44Edge = namedtuple ('Edge' , ['vertex' , 'weight' ])
55
66
7- class GraphWeighted (object ):
7+ class GraphUndirectedWeighted (object ):
88 def __init__ (self , vertex_count ):
99 self .vertex_count = vertex_count
1010 self .adjacency_list = [[] for _ in range (vertex_count )]
@@ -13,6 +13,7 @@ def add_edge(self, source, dest, weight):
1313 assert source < self .vertex_count
1414 assert dest < self .vertex_count
1515 self .adjacency_list [source ].append (Edge (dest , weight ))
16+ self .adjacency_list [dest ].append (Edge (source , weight ))
1617
1718 def get_edge (self , vertex ):
1819 for e in self .adjacency_list [vertex ]:
@@ -47,6 +48,9 @@ def dijkstra(graph, source, dest):
4748 if distances [e .vertex ] > candidate_distance :
4849 distances [e .vertex ] = candidate_distance
4950 parents [e .vertex ] = v
51+ # primitive but effective negative cycle detection
52+ if candidate_distance < - 1000 :
53+ raise Exception ("Negative cycle detected" )
5054 q .put (([distances [e .vertex ], e .vertex ]))
5155
5256 shortest_path = []
@@ -61,31 +65,22 @@ def dijkstra(graph, source, dest):
6165
6266
6367def main ():
64- g = GraphWeighted (9 )
68+ g = GraphUndirectedWeighted (9 )
6569 g .add_edge (0 , 1 , 4 )
6670 g .add_edge (1 , 7 , 6 )
6771 g .add_edge (1 , 2 , 1 )
68- g .add_edge (1 , 0 , 4 )
69- g .add_edge (2 , 1 , 1 )
7072 g .add_edge (2 , 3 , 3 )
71- g .add_edge (3 , 2 , 3 )
7273 g .add_edge (3 , 7 , 1 )
7374 g .add_edge (3 , 4 , 2 )
7475 g .add_edge (3 , 5 , 1 )
75- g .add_edge (4 , 3 , 2 )
7676 g .add_edge (4 , 5 , 1 )
77- g .add_edge (5 , 4 , 1 )
78- g .add_edge (5 , 3 , 1 )
7977 g .add_edge (5 , 6 , 1 )
80- g .add_edge (6 , 5 , 1 )
8178 g .add_edge (6 , 7 , 2 )
8279 g .add_edge (6 , 8 , 2 )
83- g .add_edge (7 , 1 , 6 )
84- g .add_edge (7 , 3 , 1 )
85- g .add_edge (7 , 6 , 2 )
8680 g .add_edge (7 , 8 , 2 )
87- g .add_edge (8 , 7 , 2 )
88- g .add_edge (8 , 6 , 2 )
81+ # for testing negative cycles
82+ # g.add_edge(1, 9, -5)
83+ # g.add_edge(9, 7, -4)
8984
9085 shortest_path , distance = dijkstra (g , 0 , 1 )
9186 assert shortest_path == [0 , 1 ] and distance == 4
0 commit comments