Equal Cost Paths

[hroyd713]

your code does not seem to support equal cost paths. If I change the edge distance from C to D from 3 to 2 and calculate the path from S to D, there are two equal costs paths (7) SACD and SD, but your code only prints SD

from dijkstra import Graph, DijkstraSPF
from dijkstra.dijkstra import AbstractDijkstraSPF

S, T, A, B, C, D, E, F, G = nodes = list("STABCDEFG")

graph = Graph()
graph.add_edge(S, A, 4)
graph.add_edge(S, B, 3)
graph.add_edge(S, D, 7)
graph.add_edge(A, C, 1)
graph.add_edge(B, S, 3)
graph.add_edge(B, D, 4)
graph.add_edge(C, E, 1)
graph.add_edge(C, D, 2)
graph.add_edge(D, E, 1)
graph.add_edge(D, T, 3)
graph.add_edge(D, F, 5)
graph.add_edge(E, G, 2)
graph.add_edge(G, E, 2)
graph.add_edge(G, T, 3)
graph.add_edge(T, F, 5)

dijkstra = DijkstraSPF(graph, S)

print("%-5s %-5s" % ("label", "distance"))
for u in nodes:
print("%-5s %8d" % (u, dijkstra.get_distance(u)))

print(" -> ".join(dijkstra.get_path(D)))

label distance
S 0
T 10
A 4
B 3
C 5
D 7
E 6
F 12
G 8
S -> D

[ahojukka5]

Well, that's how Dijkstra's algorithm is working by default. It finds the shortest path and if there are several of those, it returns one of those. Any ideas on how it could be improved?