Today’s Material

• Single Source Shortest Path Problem

– Preliminary Definitions
• Path, Cycle, Path Length, Path Cost
– Problem Description
– Dijkstra’s Algorithm
– Bellman-Ford Algorithm
 Paths
• A path is a list of vertices {v1, v2, …, vn} such that (vi, vi+1) is in E for all 1 ≤ i <
n.
– p = {A, E, B, C}
– p = {B, A, E, C, D}
A B
– p = {D, E, B, A, E, C}

D
C

• A simple path repeats no vertices

– p = {A, E, B, C}
– p = {D, A, E, B, C}
 Cycles
• A cycle is a path that starts and ends at the same vertex
– p = {A, E, B, C, D, A}
– p = {B, A, E, B}
B
– p = {D, E, B, A, E, C, D} A

D
C

• A simple cycle repeats no vertices except the first vertex is also the last
– p = {A, E, B, C, D, A}
– p = {B, A, E, B}
 Path Length and Path Cost
• Path length: the number of edges in the path
• Path cost: the sum of the costs of each edge
– Note: Path length = unweighted path cost (edge weight = 1)

2
A B
3 6

E 8
4
7 1

D
5 C

• P = {B, A, E, C, D}
• Length(p) = 4
• Cost(p) = 2+3+1+5=11
 Single Source Shortest Path Problem
• Given a graph G = (V, E) and a “source” vertex s in V, find the minimum cost paths
from s to every vertex in V

• Different variations
− unweighted vs. weighted
− positive weights only vs. negative weights allowed
− …
 Why study Shortest Path Problem?
• Optimizing traveling routes
– What is the shortest path from Queens to city X?
– What is the most fuel-efficient path from Queens to city X?

• Optimizing routing of packets on the Internet:

– Vertices = routers, edges = network links with different delays
– What is the routing path with smallest total delay?
 Unweighted Shortest Path Problem
• Problem: Given a “source” vertex s in an unweighted graph G = (V,E), find the shortest
path from s to all vertices in G

A B
F H

C Source
G

D E

• Compute shortest path from C to:

• A, B, D, E, F, G, H
 Solution Based on BFS
• Basic Idea: Starting at node s, find vertices that can be reached using 0, 1, 2, 3, …, N-
1 edges (works even for cyclic graphs!)

C
A B
F H
A D E

C Source
G
B G
D E

F
BFS Tree
Running Time? O(n+e)
rooted at C H
 What if the edges have weights?
• Does BFS still work on this graph?
– No. Minimum cost path is typically different than the minimum length path (path cost vs path
length)

2
B
• Minimum length path from C to A:
A
1 – C->A (length: 1, cost: 9)
1 – Computed by BFS
9
3
C
8 2 • Minimum cost path from C to A:
D E – C->E->D->A (length: 3, cost: 8)
3
– How do we compute this?
 Dijkstra’s Algorithm for Weighted Shortest Path (Minimum Cost
Path)
• Classic algorithm for computing shortest paths in weighted graphs (without negative
weights)

• Example of a greedy algorithm

− Irrevocably makes decisions without considering future consequences
− Not necessarily the best life strategy, but works in some cases (e.g. Huffman encoding)
 Dijkstra’s Algorithm
• Basic idea is similar to BFS
− Each vertex stores a cost for path from source
− Vertex to be expanded is the one with least path cost seen so far
− Greedy choice – always select current best vertex
− Update costs of all neighbors of selected vertex

• While BFS expands the wave on path length, Dijkstra extends the wave on path cost
 Dijkstra’s Algorithm - Sketch
• Maintain a set of vertices for which the final cost of the shortest path is known
− Initially only the cost of the shortest path to the source vertex is known – equal to 0

• Repeat until costs of all vertices are known:

1. Select the current best vertex from among the unknown vertices, i.e., the vertex with the smallest
cost, and add this vertex to the set of known vertices
2. Update costs of the neighbors of the selected vertex
 Relaxation
• Let u be the vertex selected at step 1
• Updating costs of neighbors of u is called relaxation, and is done as follows:
• There are two ways to go from s to v:
• Either follow the red path with a cost of 11
• Or, follow the blue path: First go from s to u with a cost of 3, and then take the edge (u, v) with
a cost of 5 for a total cost of 8

u
u 5 v
5 v 3
3 Relax(u, v) s 8
s 11 0
0
 Relaxation - Pseudocode

u
u 5 v
5 v 3
3 Relax(u, v) s 8
s 11 0
0

Relax(u, v){
if (cost[u] + w(u, v) < cost[v]){ // Is the path through u shorter?
cost[v] = cost[u] + w(u, v); // Yes. Then take it
pred[v] = u; // Record that we came from u
} //end-if
} //end-Relax
 Dijkstra’s Algorithm in action
2
A ∞
9 ∞ B
1. Select current best vertex – C
1
9
1 2. Add it to the known vertex set
C
3 3. Update costs of all neighbors of the
0
8 2 selected vertex
D 8
∞ 2 E
∞
3

1. Neighbor A: 0 + 9 < ∞  cost(A) = 9

2. Neighbor D: 0 + 8 < ∞  cost(D) = 8
3. Neighbor E: 0 + 2 < ∞  cost(E) = 2
 Dijkstra’s Algorithm in action
2
A 9 ∞ B
1 1. Select current best vertex – E
1
9 C 2. Add it to the known vertex set
3
0 3. Update costs of all neighbors of the
8 2
selected vertex
D 58 2 E
3

1. Neighbor D: 2 + 3 = 5 < 8  cost(D) = 5

 Dijkstra’s Algorithm in action
2
A 98 ∞ B
1. Select current best vertex – D
1
9
1 2. Add it to the known vertex set
C
3 3. Update costs of all neighbors of the
0
8 2 selected vertex
D 5 2 E
3

1. Neighbor A: 5 + 3 = 8 < 9  cost(A) = 8

 Dijkstra’s Algorithm in action

2
A 8 10
∞ B 1. Select current best vertex – A
1 2. Add it to the known vertex set
1
9 C
3 3. Update costs of all neighbors of the
0
8 2 selected vertex
D 5 2 E
3

1. Neighbor B: 8 + 2 = 10 < ∞  cost(B) = 10

 Dijkstra’s Algorithm in action

2 1. Select current best vertex – B

A 8 10 B
1 2. Add it to the known vertex set
1
9 C
3
3. Update costs of all neighbors of the
0 selected vertex
8 2

D 5 2 E
3
 Pseudocode for Dijkstra’s Algorithm
1. for all u in V do
cost[u] = ∞; pred[u] = null; O(n)
end-for n times
2. cost[s] = 0;
3. While there are unknown nodes left in the graph do
- u = Unknown node with the lowest cost O(n)
- Mark u as known
- For each node v adjacent to u do
If (cost[u] + w(u, v) < cost[v]){
cost[v] = cost[u] + w(u, v); O(e)
pred[v] = u;
end-if
end-for
end-while

Running Time? O(n+ n*n + e) = O(n2 + e)

Dense Graph: e = O(n2)  O(n2 + e) = O(n2) = O(e)
Sparse Graph: e = O(n)  O(n2 + e) = O(n2) = O(e2)
 Speeding up Dijkstra’s Algorithm
1. for all u in V do
cost[u] = ∞; pred[u] = null;
end-for DeleteMin: O(logn)
2. cost[s] = 0;
3. While there are unknown nodes left in the graph do
- u = Unknown node with the lowest cost
- Mark u as known
- For each node v adjacent to u do
If (cost[u] + w(u, v) < cost[v]){ DecreaseKey
cost[v] = cost[u] + w(u, v);
O(logn)
pred[v] = u;
end-if
end-for
end-while Running Time: O(nlogn + elogn)
• Can we implement this algorithm faster?
• Use a heap to select the lowest cost vertex O(logn)
• You now have to update the heap when the cost of the vertex changes:
DecreaseKeyO(logn)
 Dijkstra’s Algorithm: Fast Implementation
1. for all u in V do
cost[u] = ∞; pred[u] = null;
end-for
2. cost[s] = 0;
3. H = MakeHeap(V);
4. While there are unknown nodes left in the graph do
- u = DeleteMin(H);
- Mark u as known
- For each node v adjacent to u do
If (cost[u] + w(u, v) < cost[v]){
cost[v] = cost[u] + w(u, v);
DecreaseKey(H, v);
pred[v] = u;
end-if
end-for
end-while
 Implementing Dijkstra’s Algorithm in C++
• C++ priority_queue class has 3 operations only:
– top(): to get the top element without removing
– pop(): Remove the top element
– push(element): Push the element to the PQ

• As you can see, there is NO decrease_key method!

– In order to implement Dijkstra’s algorithm using C++ priority_queue, we will re-insert the vertex
into the PQ with the vertex’s new key
– This means that when we pop() the top element from the PQ, it may have already been processed
– We will check the color of the vertex to avoid re-processing
– Look at the sample C++ code
 Does Dijkstra’s algorithm always work?
• Dijkstra’s algorithm is an example of a greedy algorithm
− Greedy algorithms always make choices that currently seem the best
− Short-sighted – no consideration of long-term or global issues
− Locally optimal does not always mean globally optimal
− In Dijkstra’s case – choose the least cost node, but what if there is another path through other
vertices that is cheaper?
− Can prove: Never happens if all edge weights are positive
 Informal Proof of Correctness
Known Cloud y
s

• Assume u is the next vertex added to the known cloud

• We know that cost(u) is the minimum among unknown vertices
• We claim that cost(u) is the cost of the shortest path (red path) from s to u at the point when u is added to the known
cloud
• Assume to the contrary that this is not true
• Then there must be another path that is shorter (e.g., blue path)
• For this to be true, cost(y) must be smaller than cost(u) at the time when u is added to the known cloud. Why?
Because all edge weights are positive! This is a contradiction. QED.
 LeetCode 743. Network Delay Time
• You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times
as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the
time it takes for a signal to travel from source to target.
– We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is
impossible for all the n nodes to receive the signal, return -1.
 LeetCode 1514. Path with Maximum Probability
• You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where
edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of
traversing that edge succProb[i].
– Given two nodes start and end, find the path with the maximum probability of success to go from start to end and
return its success probability
– If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at
most 1e-5.
 Dijkstra with Negative Weights
• Dijkstra fails to compute shortest cost paths if there are edges with negative weights

• Shortest path from A to C

− Dijkstra computes: A->C, cost: 2
A
3 − Real shortest path: A->B->C, cost: 1
B

2
-2
C • What if we add a positive constant to all edge weights?
 Dijkstra with Negative Weights
• What if we add a positive constant to all edge weights and run Dijkstra on the new
graph?

3 5
A B A B
Add 2 to
2 all edge 4
-2 0
weights C
C

• Shortest path from A to C

− Dijkstra still computes: A->C
− Real shortest path: A->B->C
 Shortest Path on Graphs with Negative Edge Weights?
• We know that Dijkstra fails to work on graphs with negative edge weights

• How do compute shortest paths on graphs with negative edge weights?

• Bellman-Ford: Repeated Relaxation
 Negative Cost Cycles
• If the graph has a negative cost cycle, then the shortest paths are not defined

1
A B
2
-8
4
C D

• What’s the least cost path from A to D?

• Or to B or C?
• Least cost paths are undefined for this graph since there is a negative cost cycle: A->B-C->A
 Bellman-Ford Algorithm
• Based on the notion of performing repeated relaxations

• Basic Idea:
– Maintain a distance estimate for each vertex
– Initially set cost(s) = 0, cost(u)=∞ for all other vertices
– Progressively perform relaxation over all edges until shortest cost paths are computed

• The algorithm also finds whether the graph has any negative weight cycles
 Belman-Ford Algorithm Implementation
BellmanFord(G, w, s){
For each (u in V) { // Initialization
cost[u] = +∞
prev[u] = nil Running Time?
} //end-for
n-1 times O(n*e)
cost[s] = 0;
for i=1 to n-1 do {
for each edge (u, v) e E {
if (cost[u] + w(u, v) < cost[v]) { // Relax
cost[v] = cost[u] + w(u, v);
pred[v] = u; O(e)
} //end-if
} //end-for
} //end-for

for each edge (u, v) e E do{

if (cost[u] + w(u, v) < cost[v]) then
return FALSE;
} //end-for

return TRUE;
} //end-BellmanFord
 Bellman-Ford Algorithm: Example

B Vertex Cost Pred

4
A 0 ∞
4 -3 A 0 -
-2 B ∞
4 A-
3 2 1 E
∞
C 23
∞ A-
B
1 -1
C 23
∞ ∞
6 D D ∞
6 B-
E 1
∞ B-

(C, D) (A, B) (A, C) (B, C) (B, D) (B,

(B,E)
E) (D,
(D,E)
E)

First Iteration
 Bellman-Ford Algorithm: Example

B Vertex Cost Pred

4
A 0 4 -3 A 0 -
-2 E B 4 A
3 2 1
C 2 B
1 -1
C 2 63 D 36 C
B
D
E 1 B

(C, D) (A, B) (A, C) (B, C) (B, D) (B,

(B,E)
E) (D,
(D,E)
E)

Second Iteration
 Bellman-Ford Algorithm: Example

B Vertex Cost Pred

4
A 0 4 -3 A 0 -
-2 E B 4 A
3 2 1
C 2 B
1 -1
C 2 3 D 3 C
D
E 1 B

(C, D) (A, B) (A, C) (B, C) (B, D) (B,

(B,E)
E) (D,
(D,E)
E)

Third & Fourth Iteration

 Bellman-Ford Algorithm: Final Result

4 B
A 0 4 A 0
-3
-2 E 4
3 2 1
-1 B 4
1
C 2 3 -3
D -2

C 2 1 E

Vertex Cost Pred 1

A 0 -
D 3
B 4 A
C 2 B
D 3 C
E 1 B
 LeetCode 743. Network Delay Time
• You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times
as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the
time it takes for a signal to travel from source to target.
– We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is
impossible for all the n nodes to receive the signal, return -1.
 LeetCode Problems
• 743. Network Delay Time
• 1514. Path with Maximum Probability
• 1631. Path With Minimum Effort
• 1976. Number of Ways to Arrive at Destination
• 2812. Find the Safest Path in a Grid