- Input: A graph G with non-negative edge weights, a source vertex s and a target vertex t.
- Output: The shortest path between s and t in G.
- O((|E| + |V |)log |V |) is pretty fast, right?
- For a graph of USA with 20M vertices and 50M edges it will work for several seconds on average
- Millions of users of Google Maps want the result in a blink of an eye, all at the same time
When a vertex u is selected via ExtractMin, dist[u] = d(s, u).
- When a vertex is extracted from the priority queue for processing, all the vertices at smaller distances have already been processed
- A “circle” of processed vertices grows
- In 1929, Hungarian mathematician Frigyes Karinthy made a “Small World” conjecture
- Can pass a message from any person toany person in at most 6 handshakes
- This is close to truth according to experiments and is called a “six handshakes” or “six degrees of separation” idea
- Dijkstra goes in “circles”
- Bidirectional search idea can reduce the search space
- Roughly 2x speedup for road networks
- Meet-in-the-middle — N^(1/2) instead of N
- 1000 times faster for social networks
- To find the shortest path from s to t
- Initialize dist[s] to 0, all other distances to ∞
- ExtractMin — choose unprocessed u with the smallest dist[u]
- Process u — Relax the edges outgoing from u
- Repeat until t is processed
Reversed graph G^R for a graph G is the graph with the same set of vertices V and the set of reversed edges E^R, such that for any edge (u, v) ∈ E there is an edge (v, u) ∈ E^R and vice versa.
- Build G^R
- Start Dijkstra from s in G and from t in G^R
- Alternate between Dijkstra steps in G and in G^R
- Stop when some vertex v is processed both in G and in G^R
- Compute the shortest path between s and t
Let v be the first vertex which is processed both in G and in G^R. Does it follow that there is a shortest path from s to t going through v?
No.
Let dist[u] be the distance estimate in the forward Dijkstra from s in G and distR [u] — the same in the backward Dijkstra from t in G^R. After some node v is processed both in G and G^R, some shortest path from s to t passes through some node u which is processed either in G, in G^R, or both, and d(s,t) = dist[u] + dist^R[u].
BidirectionalDijkstra(G,s,t)
G^R ← ReverseGraph(G)
Fill dist, dist^R with +∞ for each node
dist[s] ← 0, dist^R[t] ← 0
Fill prev, prev^R with None for each node
proc ← empty, proc^R ← empty
do:
v ← ExtractMin(dist)
Process(v, G, dist, prev, proc)
if v in proc^R:
return ShortestPath(s, dist, prev, proc,t, . . .)
v^R ← ExtractMin(dist^R)
repeat symmetrically for v^R as for v
while True
Relax(u, v, dist, prev)
if dist[v] > dist[u] + w(u, v):
dist[v] ← dist[u] + w(u, v)
prev[v] ← u
Process(u, G, dist, prev, proc)
for (u, v) ∈ E(G):
Relax(u, v, dist, prev)
proc.Append(u)
ShortestPath(s, dist, prev, proc,t, dist^R, prev^R, proc^R)
distance ← +∞, ubest ← None
for u in proc + proc^R:
if dist[u] + dist^R
[u] < distance:
u_best ← u
distance ← dist[u] + dist^R[u]
path ← empty
last ← ubest
while last ̸= s:
path.Append(last)
last ← prev[last]
path ← Reverse(path)
last ← u_best
while last ̸= t:
last ← prev^R[last]
path.Append(last)
return (distance, path)
- Worst-case running time of Bidirectional Dijkstra is the same as for Dijkstra
- Speedup in practice depends on the graph
- Memory consumption is 2x to store G and G^R
- You’ll see the speedup on social network graph in the Programming Assignment