Implementação do Algoritmo de Dijkstra em Python
Enviado por
gogere6620Implementação do Algoritmo de Dijkstra em Python
Enviado por
gogere6620Exercício – POO
1) Escreve um programa em Python para representar um grafo direcionado e valorado. A grafo deve
ser representado como um Dicionário em que cada elemento tem como chave um string que
representa um vértice e o valor associado a essa chave é um Dicionário com as distâncias para os
vértices adjacentes. Por exemplo:
{ 'A': {'B': 50, 'C': 30, 'D': 100, 'E': 10},
'B': {'A': 50, 'C': 5, 'D': 20},
'C': {'A': 30, 'B': 5, 'D': 50},
'D': {'A': 100, 'B': 20, 'C': 50, 'E': 10},
'E': {'A': 10, 'D': 10}
}
Representa o seguinte grafo:
Implemente o algoritmo que, dados um vértice inicial, encontra o menor caminho entre ele e todos
os outros vértices. ([Link]
O seu programa vai ler a entrada no formato mostrado abaixo.
Exemplo de entrada:
S.J.Rio_Preto
São_Carlos 207
Ribeirão_Preto 211
São_Carlos
S.J.Rio_Preto 207
Ribeirão_Preto 100
Rio_Claro 65
Ribeirão_Preto
Limeira 174
São_Carlos 100
S.J.Rio_Preto 211
Limeira
Rio_Claro 38
Ribeirão_Preto 174
Campinas 55
Mogi_Mirim 59
Rio_Claro
Limeira 38
São_Carlos 65
Campinas
Limeira 55
Mogi_Mirim 61
Mogi_Mirim
Limeira 59
Campinas 61
Saída: deve ser apresentada, para cada cidade, a menor distância para todas demais. Um trecho da
saída para o exemplo acima:
S.J.Rio_Preto para Limeira
Distancia: 310,0
Caminho: --> São_Carlos --> Rio_Claro --> Limeira
S.J.Rio_Preto para Rio_Claro
Distancia: 272,0
Caminho: --> São_Carlos --> Rio_Claro
S.J.Rio_Preto para Ribeirão_Preto
Distancia: 211,0
Caminho: --> Ribeirão_Preto
S.J.Rio_Preto para Mogi_Mirim
Distancia: 369,0
Caminho: --> São_Carlos --> Rio_Claro --> Limeira --> Mogi_Mirim
S.J.Rio_Preto para São_Carlos
Distancia: 207,0
Caminho: --> São_Carlos
S.J.Rio_Preto para Campinas
Distancia: 365,0
Caminho: --> São_Carlos --> Rio_Claro --> Limeira --> Campinas
---------------------------------------------
Limeira para S.J.Rio_Preto
Distancia: 310,0
Caminho: --> Rio_Claro --> São_Carlos --> S.J.Rio_Preto
Limeira para Rio_Claro
Distancia: 38,0
Caminho: --> Rio_Claro
Limeira para Ribeirão_Preto
Distancia: 174,0
Caminho: --> Ribeirão_Preto
Limeira para Mogi_Mirim
Distancia: 59,0
Caminho: --> Mogi_Mirim
Limeira para São_Carlos
Distancia: 103,0
Caminho: --> Rio_Claro --> São_Carlos
Limeira para Campinas
Distancia: 55,0
Caminho: --> Campinas