-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathall_pairs_shortest_paths.py
157 lines (132 loc) · 6.04 KB
/
all_pairs_shortest_paths.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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
# In this assignment you will implement one or more algorithms for the
# all-pairs shortest-path problem. Here are data files describing three graphs:
# g1.txt, g2.txt, g3.txt
# The first line indicates the number of vertices and edges, respectively. Each
# subsequent line describes an edge (the first two numbers are its tail and
# head, respectively) and its length (the third number).
# NOTE: some of the edge lengths are negative.
# NOTE: These graphs may or may not have negative-cost cycles.
# Your task is to compute the shortest shortest path. Precisely, you must first
# identify which, if any, of the three graphs have no negative cycles. For each
# such graph, you should compute all-pairs shortest paths and remember the
# smallest one (i.e., compute min(u,v) d(u,v) where d(u,v) denotes the
# shortest-path distance from u to v).
# If each of the three graphs has a negative-cost cycle, then enter "NULL" in
# the box below. If exactly one graph has no negative-cost cycles, then enter
# the length of its shortest shortest path in the box below. If two or more of
# the graphs have no negative-cost cycles, then enter the smallest of the
# lengths of their shortest shortest paths in the box below.
# OPTIONAL: You can use whatever algorithm you like to solve this question. If
# you have extra time, try comparing the performance of different all-pairs
# shortest-path algorithms!
# OPTIONAL: Here is a bigger data set to play with: large.txt. For fun, try
# computing the shortest shortest path of the graph in the file above.
from collections import defaultdict
from dijkstra import dijkstra
def bellman_ford(graph, num_vertices, source):
# prev_dist: shortest path distance with at most i-1 hops
# curr_dist: shortest path distance with at most i hops
# predecessor: second-to-last vertex on the shortest path
prev_distances = [float('inf')]
curr_distances = [float('inf')]
predecessors = [None]
# at the beginning, all vertices have a distance of infinity
# and no predecessor
for v in range(num_vertices):
prev_distances.append(float('inf'))
curr_distances.append(float('inf'))
predecessors.append(None)
# the distance of the source to itself is 0
prev_distances[source] = 0
curr_distances[source] = 0
# perform an extra iteration in order to detect negative cost cycles
for i in range(1, num_vertices + 1):
# the distance with at most i hops is the minimum of
# the distance with at most i-1 hops to the vertex and
# the distances with at most i-1 hops to a neighbouring vertex
# plus the weight of edge connecting the neighbour to the vertex
curr_distances[i] = prev_distances[i]
predecessors[i] = predecessors[i]
for tail in graph[i]:
weight = graph[i][tail]
if prev_distances[tail] + weight < curr_distances[i]:
curr_distances[i] = prev_distances[tail] + weight
predecessors[i] = tail
# cache the results of the current iteration for the next iteration
prev_distances = curr_distances
# if the shortest path distance for any vertex has changed after the
# nth iteration, the graph contains a negative cost cycle, so bail out
if prev_distances != curr_distances:
raise AssertionError('The graph contains a negative cost cycle!')
# otherwise, return the shortest path distances and predecessors
return curr_distances, predecessors
def johnson(graph, num_vertices):
shortest_distances = {}
# add a new vertex 0 to the graph that is
# connected to all of the other vertices with weight 0
for i in range(1, num_vertices):
graph[i][0] = 0
# run the Bellman-Ford algorithm on the graph with vertex 0 as the source
# to find the shortest path distances from the source vertex to each of the
# other vertices. If a negative cycle is detected, terminate the algorithm
try:
distances, predecessors = bellman_ford(graph, num_vertices, 0)
# remove the vertex 0 from the graph
for i in range(1, num_vertices):
del graph[i][0]
reversed_graph = reverse_graph(graph)
for i in range(1, num_vertices):
# re-weight the edges of the original graph using the values
# computed by the Bellman-Ford algorithm, to w(u, v) + h(u) - h(v)
for tail in graph[i]:
graph[i][tail] += distances[tail] - distances[i]
# run Dijkstra's algorithm n times to find the shortest path
# distances from each vertex to every other vertex
shortest_distances[i] = dijkstra(reversed_graph, num_vertices, i)
return shortest_distances
except AssertionError as err:
print(str(err))
def make_graph(filename):
# represent the graph as a nested dictionary
# the keys are the head vertices and the values are
# another dictionary in which the keys are
# the tail vertices which lead to the head vertices and
# the values are the weights of the edges
graph = defaultdict(dict)
with open(filename, 'r') as f:
num_vertices, num_edges = [int(n) for n in next(f).split()]
for line in f:
tail, head, weight = [int(n) for n in line.split()]
graph[head][tail] = weight
return graph, num_vertices
def reverse_graph(graph):
reversed_graph = defaultdict(dict)
for head in graph.keys():
for tail in graph[head]:
reversed_graph[tail][head] = graph[head][tail]
return reversed_graph
def main():
# filenames = ['g1.txt', 'g2.txt', 'g3.txt']
# for filename in filenames:
# graph, num_vertices = make_graph(filename)
# print(johnson(graph, num_vertices))
graph = {
1: {},
2: {
1: 2, # s -> v: 2
},
3: {
1: 4, # s -> x: 4
2: 1, # v -> x: 1
},
4: {
2: 2, # v -> w: 2
},
5: {
3: 4, # x -> t: 4
4: 2, # w -> t: 2
},
}
print(johnson(graph, 5))
if __name__ == '__main__':
main()