@@ -42,8 +42,9 @@ def dijkstra(graph, source, dest):
42
42
v = v_tuple [1 ]
43
43
44
44
for e in graph .get_edge (v ):
45
- if distances [e .vertex ] > distances [v ] + e .weight :
46
- distances [e .vertex ] = distances [v ] + e .weight
45
+ candidate_distance = distances [v ] + e .weight
46
+ if distances [e .vertex ] > candidate_distance :
47
+ distances [e .vertex ] = candidate_distance
47
48
parents [e .vertex ] = v
48
49
q .put (([distances [e .vertex ], e .vertex ]))
49
50
@@ -85,12 +86,14 @@ def main():
85
86
g .add_edge (8 , 7 , 2 )
86
87
g .add_edge (8 , 6 , 2 )
87
88
88
- print ("Graph created" )
89
+ shortest_path , distance = dijkstra (g , 0 , 8 )
90
+ assert shortest_path == [0 , 1 , 2 , 3 , 7 , 8 ] and distance == 11
89
91
90
- shortest_path , distance = dijkstra (g , 8 , 2 )
92
+ shortest_path , distance = dijkstra (g , 5 , 0 )
93
+ assert shortest_path == [5 , 3 , 2 , 1 , 0 ] and distance == 9
91
94
92
- print ( "shortest path:" , shortest_path )
93
- print ( "distance:" , distance )
95
+ shortest_path , distance = dijkstra ( g , 1 , 1 )
96
+ assert shortest_path == [ 1 ] and distance == 0
94
97
95
98
96
99
if __name__ == "__main__" :
0 commit comments