-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathshortest_path.py
More file actions
273 lines (261 loc) · 11.8 KB
/
shortest_path.py
File metadata and controls
273 lines (261 loc) · 11.8 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
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
## Graph Algorithm Exercise Part I: COMPUTATION OF SHORTEST PATHS
##################### SOME FAMOUS SHORTEST PATH ALGORITHMS #######
## 1. Dijkstra Algorithm: single-source, nonnegative shortest path
## 2. Bellman-Ford Algorithm: single-source, weights could be negative
## 3. A* search: single-pair, use heuristics to speed up the search
## 4. Floyd-Warshall Algorithm: all-pairs shortest paths
## 5. Johnson's Algorithm: all pairs shortest paths, may be faster
## than Floyd-Warshall on sparse graphs
## 6. Perturbation theory: finds (at worst) the locally shortest path
##################################################################
INF = float('inf')
## Dijkstra Algorithm
## Given a directed weighted graph, find the minimal travel cost from
## a certain node to all other nodes in time O(n**3)
## Dijkstra Algorithm essentially has a flavor of Dynamic Programming
## AHA: ###################
## 1. DATA STRUCTURES: unvisted (vertex set), distances (hash), current (single vertex)
## 2. INITIALIZATION: unvisited = all vertices (including start),
## distances (0 for start, INF for rest), current (start)
## 3. UPDATE:
## (1) distances: update distances all unvisted neighbors of current node
## (2) unvisited: a vertex remains unvisited till all its neighbors have been checked
## (3) current: pick the vertex with minimal distance from unvisited
## 4. TERMINATION: if unvisited is empty OR all vertices in unvisted have dist of INF
## 5. BONUS: precedences (hash of vertex->vertex) can be used to track the path
## it is like the track of the reverse of the shortest path
def dijkstra_shortest_path(start, graph):
unvisited = set(graph.keys())
distances = dict([(v, 0 if v == start else INF) for v in graph.keys()])
precedences = {start: None}
while unvisited:
current = min(unvisited, key = lambda v: distances[v])
if distances[current] == INF:
break
for v, current_to_v in graph[current].items():
if (v in unvisited and
current_to_v+distances[current] < distances[v]):
distances[v] = current_to_v+distances[current]
precedences[v] = current
unvisited.remove(current)
def restore_paths():
paths = dict((v, [v]) for (v, _v) in precedences.items() if _v is None)
while len(paths) < len(precedences):
paths.update(dict([
(v, paths[u] + [v])
for u in paths
for (v, _v) in precedences.items()
if _v == u
]))
return paths
shortest_paths = restore_paths()
return distances, shortest_paths
## A* Search Algorithm
## heuristic function h must be admissible for Astar to be
## adminissable (optimal). An admissable h means it never
## overestimates the actual minimal cost of reaching the goal
## IN GENERAL: Dijkstra algorithm can be viewed as a special case
## of A* where h(x) = C for all x. And General Depth-First Search
## can be implemented using A* by considering that there is a global
## counter C initialized with a very large value. Every time we process
## a node we asign C to all of its newly discovered neighbors, and decreasing
## Counter by 1 after assignment.
############ AHA:
## Same search framework as traversal, backtracking, and etc.
## Main difference is the frontier strucutre, here it is based on
## priority queue where priority is calcuated as "cost + heuristic"
def astar_shortest_path(start, end, graph, h = None):
## default heuristic function - essentially dijkstra search
if not h:
h = lambda v: 0
explored, frontier = set(), [start]
precedences = {start: [start]}
distances = {start: 0}
while frontier:
frontier = sorted(frontier, key = lambda v: distances[v] + h(v))
current = frontier.pop(0)
if current in explored:
continue
explored.add(current)
if current == end:
break
for v, current2v in graph[current].items():
frontier.append(v)
if (v not in distances or
current2v+distances[current] < distances[v]):
distances[v] = current2v + distances[current]
precedences[v] = precedences[current] + [v]
return distances[end], ''.join(precedences[end])
## Floyd Warshall Algorithm
## Finding the transitive closure and shortest paths between
## all pairs in a weighted graph. The original algorithm assumes
## there is no negative cycles in the graph, and if they do exist,
## the Floyd-Warshall algorithm can be used to detect them.
## It is essentially an example of dynamic programming, running in O(n**3)
## THE KEY TO IMPLEMENT DYNAMIC PROGRAMMING IS TO ASK THE QUESTION:
## IF YOU ALREADY GOT THE CURRENT SOLUTION, WHAT'S THE IMMEDIATE
## NEXT THING TO CALCULATE?
## IN THIS CASE, WE KNOW THE SHORTEST DISTANCE FROM I TO J IF
## WE ALREADY KNOW THE SHORTEST DISTANCE FROM I TO ALL THE NEIGHBORS
## J
###### AHA:
## the shortest path from i to j is the min of all paths i->k->j
## over all possible intermediate vertices k
## 1. DYNAMIC PROGRAMMING VERSION
############################################################
## CONSIDER THE SHORTEST_PATH TABLE INDEXED BY (I, J, K) THAT
## RETURNS THE SHORTEST POSSIBLE PATH FROM I TO J VIA INTERMEDIATE
## POINTS FROM (V1, V2, ..., VK). GIVEN THAT, THE NEXT IMMEDIATE
## RESULT WOULD BE (I, J, K+1), I.E., THROUGH VIA-POINTS (V1, V2, ..., VK+1)
##
## CLEARLY, THERE ARE TWO CANDIDATES FOR THE PATHS: EITHER THE REAL
## SHORTEST PATH USES ONLY VERTICES IN SET {1,...,K} OR THERE
## EXISTS SOME PATH THAT GOES FROM I TO K+1, THEN FROM K+1 TO J.
## AND THE SECOND CANDIDATE CAN BE REPRESENTED AS:
## (SHORTEST FROM I TO K+1 THROUGH 1,...,K) + (SHORTEST FROM K+1 TO J THROUGH 1,...,K)
## THAT IS WHERE THE RECURSION REALLY LIES. I.E.,
## shortest(i, j, k+1) = min(shortest(i, j, k),
## shortest(i, k+1, k) + shortest(k+1, j, k))
############################################################
def floyd_warshall_algorithm_dp(graph):
distances = dict([
((u, v),
(0 if u is v
else graph[u][v] if v in graph[u]
else INF))
for u in graph
for v in graph
])
## THE ORDER OF THE LOOP IS BEAUTIFUL!
## the loop for k is not for every single k
## is for interval from 1, 1..2, ..., 1..k
for k in graph: # use intermediate vertices up to k
for i in graph: # update shortest distance pair i -> j
for j in graph:
distances[(i, j)] = min(distances[(i, j)],
distances[(i, k)] + distances[(k, j)])
return distances
## 2. MEMOIZATION VERSION
############################################################
## A VERY GOOD EXAMPLE OF USING HISTORY PARAMETER
## TO AVOID CYCLE-RECURSION IN MEMOIZATION IMPLEMENTATION
############################################################
def floyd_warshall_algorithm_memo(graph):
def neighbors_to(v):
return [u for u in graph if v in graph[u]]
def shortest_dist(start, end, explored = None):
if explored is None: explored = set()
## redefine distances every time for new u, v
## because the calculated distances for different u, v
## are not the same
distances = dict([
((u, u), 0)
for u in graph
])
if (start, end) not in distances:
candidates = [
shortest_dist(start, via, explored | set([end])) + graph[via][end]
for via in neighbors_to(end)
if via not in explored
]
distances[(start, end)] = min(candidates) if candidates else INF
return distances[(start, end)]
shortest_distances = dict([
((u, v), shortest_dist(u, v))
for u in graph
for v in graph
])
return shortest_distances
#################Applicaitons of Shortest Path
##### Baggage Allowance Problem
## There are n airports. For every i and j we know the
## baggage allowance on the flights from ith to jth.
## For a given starting point a and for all other airports
## x find the maximal weight that can be transported from
## a to x (using as many intermediate stops as necessary).
## The algorithm should run in time O(n**2)
## AHA: use the max instead of sum in Dijkstra algorithm (single source)
def baggage_allowance(graph, start):
unvisited = set(graph.keys())
allowances = dict([
(u, 0 if u is start else -INF)
for u in graph
])
came_from = {start: []}
while unvisited:
current = max(unvisited, key = lambda v: allowances[v])
if allowances[current] == -INF:
break
for v in graph[current]:
if allowances[v] < max(graph[current][v], allowances[current]):
allowances[v] = max(graph[current][v], allowances[current])
came_from[v] = came_from[current] + [v]
unvisited.remove(current)
return allowances, came_from
## tests
if __name__ == '__main__':
## some common test examples
g1 = {
'A': {'B': 5, 'C': 2},
'B': {'E': 1},
'C': {'B': 1, 'D': 1},
'D': {'B': 2, 'F': 6},
'E': {'A': 1},
'F': dict()
}
## test shortest_path from a certain start node
shortest_distances, shortest_paths = dijkstra_shortest_path('A', g1)
assert shortest_distances == {'A': 0, 'C': 2, 'B': 3, 'E': 4, 'D': 3, 'F': 9}
assert shortest_paths == {
'A': ['A'], 'C': ['A', 'C'], 'B': ['A', 'C', 'B'],
'E': ['A', 'C', 'B', 'E'], 'D': ['A', 'C', 'D'],
'F': ['A', 'C', 'D', 'F']}
## test astar_shortest_path
## with a very specific heuristic function
shortest_distances, shortest_paths = astar_shortest_path('A', 'B', g1,
h = lambda v: 1 if 'B' in g1[v] else 2)
assert shortest_distances == 3
assert shortest_paths == 'ACB'
## test floyd_warshall_algorithm memoization version
assert floyd_warshall_algorithm_memo(g1) == {
('F', 'B'): INF, ('E', 'F'): 10, ('D', 'D'): 0,
('B', 'A'): 2, ('D', 'E'): 3, ('A', 'F'): 9,
('B', 'F'): 11, ('C', 'D'): 1, ('A', 'B'): 3,
('F', 'C'): INF, ('E', 'A'): 1, ('B', 'B'): 0,
('E', 'E'): 0, ('D', 'A'): 4, ('C', 'C'): 0,
('D', 'B'): 2, ('B', 'C'): 4, ('A', 'A'): 0,
('E', 'D'): 4, ('A', 'E'): 4, ('F', 'F'): 0,
('F', 'D'): INF, ('A', 'D'): 3, ('E', 'C'): 3,
('B', 'D'): 5, ('C', 'F'): 7, ('F', 'A'): INF,
('D', 'C'): 6, ('D', 'F'): 6, ('A', 'C'): 2,
('F', 'E'): INF, ('C', 'A'): 3, ('E', 'B'): 4,
('C', 'B'): 1, ('B', 'E'): 1, ('C', 'E'): 2}
## test floyd_warshall_algorithm dynamic programming version
assert floyd_warshall_algorithm_dp(g1) == {
('F', 'B'): INF, ('E', 'F'): 10, ('D', 'D'): 0,
('B', 'A'): 2, ('D', 'E'): 3, ('A', 'F'): 9,
('B', 'F'): 11, ('C', 'D'): 1, ('A', 'B'): 3,
('F', 'C'): INF, ('E', 'A'): 1, ('B', 'B'): 0,
('E', 'E'): 0, ('D', 'A'): 4, ('C', 'C'): 0,
('D', 'B'): 2, ('B', 'C'): 4, ('A', 'A'): 0,
('E', 'D'): 4, ('A', 'E'): 4, ('F', 'F'): 0,
('F', 'D'): INF, ('A', 'D'): 3, ('E', 'C'): 3,
('B', 'D'): 5, ('C', 'F'): 7, ('F', 'A'): INF,
('D', 'C'): 6, ('D', 'F'): 6, ('A', 'C'): 2,
('F', 'E'): INF, ('C', 'A'): 3, ('E', 'B'): 4,
('C', 'B'): 1, ('B', 'E'): 1, ('C', 'E'): 2}
## test baggage allowance problem
travel = {
'A': {'B': 2, 'C': 2, 'D': 5},
'B': dict(),
'C': {'E': 3},
'D': {'E': 3},
'E': dict(),
'F': dict()
}
allowances, routes = baggage_allowance(travel, 'A')
assert allowances == {'A': 0, 'C': 2, 'B': 2, 'E': 5, 'D': 5, 'F': -INF}
assert routes == {
'A': [], 'C': ['C'],
'B': ['B'], 'E': ['D', 'E'], 'D': ['D']}
print 'all tests pass'