10000 Completed shortest paths. · anubhavcoder/practice-python@6fa1f06 · GitHub
[go: up one dir, main page]

Skip to content

Commit 6fa1f06

Browse files
committed
Completed shortest paths.
1 parent b62825d commit 6fa1f06

File tree

1 file changed

+9
-6
lines changed

1 file changed

+9
-6
lines changed

graphs/dijkstra.py

Lines changed: 9 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -42,8 +42,9 @@ def dijkstra(graph, source, dest):
4242
v = v_tuple[1]
4343

4444
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
4748
parents[e.vertex] = v
4849
q.put(([distances[e.vertex], e.vertex]))
4950

@@ -85,12 +86,14 @@ def main():
8586
g.add_edge(8, 7, 2)
8687
g.add_edge(8, 6, 2)
8788

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
8991

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
9194

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
9497

9598

9699
if __name__ == "__main__":

0 commit comments

Comments
 (0)
0