-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstra.py
56 lines (51 loc) · 1.92 KB
/
dijkstra.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import bintrees
from typing import Tuple, List
from math import inf
from graph_commons import AdjacentListGraph, SPVertice
def dijkstra_shortest_paths(graph: AdjacentListGraph, start: SPVertice):
visited = set()
for v in graph.vertices:
v.shortest_path_estimate = inf
start.shortest_path_estimate = 0
q = bintrees.RBTree()
for v in graph.vertices:
q.insert(v, v.shortest_path_estimate)
while not q.is_empty():
u, current_sp_eta = q.min_item()
q.remove(u)
visited.add(u)
for adj_v, w in graph[u].items():
if adj_v in visited:
continue
if adj_v.shortest_path_estimate > current_sp_eta + w:
adj_v.previous = u
q.remove(adj_v)
adj_v.shortest_path_estimate = current_sp_eta + w
q.insert(adj_v, adj_v.shortest_path_estimate)
def dijkstra_shortest_path(graph: AdjacentListGraph, start: SPVertice, end: SPVertice) -> Tuple[int, List[SPVertice]]:
visited = set()
for v in graph.vertices:
v.shortest_path_estimate = inf
start.shortest_path_estimate = 0
q = bintrees.RBTree()
for v in graph.vertices:
q.insert(v, v.shortest_path_estimate)
while not q.is_empty():
u, current_sp_eta = q.min_item()
q.remove(u)
visited.add(u)
if u == end:
shortest_path = [u]
while u.previous:
u = u.previous
shortest_path.append(u)
return end.shortest_path_estimate, list(reversed(shortest_path))
for adj_v, w in graph[u].items():
if adj_v in visited:
continue
if adj_v.shortest_path_estimate > current_sp_eta + w:
adj_v.previous = u
q.remove(adj_v)
adj_v.shortest_path_estimate = current_sp_eta + w
q.insert(adj_v, adj_v.shortest_path_estimate)
return inf, []