Repository navigation
Expand file tree
/
Copy pathdag_shortest_paths.py
More file actions
50 lines (41 loc) · 1.7 KB
/
Copy pathdag_shortest_paths.py
File metadata and controls
50 lines (41 loc) · 1.7 KB
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
import math
from depth_first_search import depth_first_search
def dag_shortest_paths(G, w, start_vertex):
traversal = depth_first_search(G)
ordering = traversal.get_topological_order(G, start_vertex)
distance_est = {vertex: math.inf for vertex in G.vertices()}
distance_est[start_vertex] = 0
spt_predecessor = {vertex: None for vertex in G.vertices()}
n = len(ordering)
for i in range(n):
source = ordering[i]
for edge in G.incident_edges(source):
destination = edge.opposite(source)
if distance_est[destination] > distance_est[source] + w[edge]:
distance_est[destination] = distance_est[source] + w[edge]
spt_predecessor[destination] = source
return distance_est, spt_predecessor
if __name__ == '__main__':
import graph
E = [('a', 'b', 4), ('b', 'd', 10),
('d', 'f', 11), ('b', 'c', 5),
('a', 'c', 2), ('c', 'e', 3),
('e', 'd', 4)]
print('Shortest paths from a for graph')
print(E)
G, weight_mapping = graph.create_graph(E, is_directed=True)
start_vertex = G.get_vertex('a')
d, p = dag_shortest_paths(G, weight_mapping, start_vertex)
for key in p:
if p[key] is None:
print(key.element() + ' is the start vertex')
else:
path = [key]
vertex = p[key]
while not (vertex is None):
path.insert(0, vertex)
vertex = p[vertex]
elements = [vertex.element() for vertex in path]
print('Shortest path to ' + key.element() + ' with value: ' + str(d[key]))
x = '->'.join(elements)
print(x)