Algoritmo de Dijkstra
Ler um arquivo que contém na primeira linha o número N de cidades que serão consideradas no seu algoritmo [10, 50] e nas demais N linhas o nome da cidade e seus respectivos pontos de coordenadas de um plano 2D (x, y).;
• Caso utilize a representação do grafo utilizando matriz, esta deverá ser declarada dinamicamente;
• Crie uma função capaz de gerar artificialmente os arcos que existirão entre os nós do seu grafo. Essa função deverá ter como parâmetro um número entre 1 e 100, que representa a porcentagem de arcos existentes entre os nós. Para saber quais serão os arcos, faça um sorteio. Uma sugestão para teste inicial é utilizar uma porcentagem de 50%. Caso esteja muito restritivo ou encontrando muitos caminhos mínimos diretos entre dois nós, faça o ajuste da porcentagem para mais ou menos. Ao sortear, você já pode chamar a função abaixo para realização do cálculo.
• Para descobrir qual é a distância entre dois pontos quaisquer, você deverá efetuar o cálculo da distância Euclidiana entre tais pontos. Esse cálculo será utilizado para o cálculo do caminho mínimo;
• Efetuar o cálculo do caminho mínimo entre dois pontos quaisquer utilizando para isso o Algoritmo de Dijkstra. O usuário durante a execução pode executar a consulta do caminho mínimo quantas vezes quiser, logo, providencie um mecanismo de menus que permita o usuário executar seu programa até que uma determinada condição seja satisfeita;
• Permita que o usuário saiba qual será o caminho mínimo que ele deverá percorrer, cidade a cidade, para chegar de uma cidade a outra.
• Crie uma estrutura de dados para armazenar pelo menos o nome da cidade e suas coordenadas x e y.