Cześć, potrzebuję pomocy z implementacją algorytmu Dijkstry w Pythonie.
Obecnie kod wygląda następująco:
class Graph ():
def __init__(self):
self.nodes = set()
self.edges = defaultdict(list)
self.distances = {}
def add_node(self, value):
self.nodes.add(value)
def add_edge(self, from_node, to_node, distance):
self.edges[from_node].append(to_node)
self.edges[to_node].append(from_node)
self.distances[(from_node, to_node)] = distance
self.distances[(to_node, from_node)] = distance
def dijsktra(graph, initial):
visited = {initial: 0}
path = {}
nodes = set(graph.nodes)
while nodes:
min_node = None
for node in nodes:
if node in visited:
if min_node is None:
min_node = node
elif visited[node] < visited[min_node]:
min_node = node
if min_node is None:
break
nodes.remove(min_node)
current_weight = visited[min_node]
for edge in graph.edges[min_node]:
weight = current_weight + graph.distances[(min_node, edge)]
if edge not in visited or weight < visited[edge]:
visited[edge] = weight
path[edge] = min_node
return visited, path
Tutaj przykład
g = Graph()
g.add_node('a')
g.add_node('b')
g.add_node('c')
g.add_node('d')
g.add_node('e')
g.add_edge('a', 'b', 10)
g.add_edge('b', 'c', 10)
g.add_edge('a', 'c', 15)
g.add_edge('c', 'd', 20)
g.add_edge('d','e',3)
print(dijsktra(g, 'a'))
W wyniku otrzymuję coś takiego
({'a': 0, 'b': 10, 'c': 15, 'd': 35, 'e': 38}, {'b': 'a', 'c': 'a', 'd': 'c', 'e': 'd'})
Natomiast potrzebuję, by odpowiedź wyglądała mniej więcej w taki sposób:
({'a': 0, 'b': 10, 'c': 15, 'd': 35, 'e': 38}, {'b': 'a', 'c': 'a', 'd': 'c','a', 'e': 'd','c','a'})
Dziękuję za wszelką pomoc!
Nie jest to mój program i nie używam go w takiej wersji, taki sam problem miałam ze swoim programem, odpowiedź była niezbędna do możliwości zmiany swojej wersji.