Shortest Path Problems: Dijkstra, Bellman-Ford,
and Floyd-Warshall
Duke COMPSCI 309s
Siyang Chen
Spring 2014
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
General Graph Search
Let q be some sort of abstract queue object, which supports the
following two operations:
1. add, which adds a node into q
2. popFirst, which pops the ‘first’ node from q
Here the definition of ‘first’ depends on the specific queue
implementation.
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
General Graph Search
Let q be some sort of abstract queue object, which supports the
following two operations:
1. add, which adds a node into q
2. popFirst, which pops the ‘first’ node from q
Here the definition of ‘first’ depends on the specific queue
implementation.
Then we can formulate all graph search algorithms in the following
manner:
▶ While q is not empty:
▶ v ← q.popFirst()
▶ For all neighbours u of v such that u ̸∈ q:
▶ Add u to q
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
General Graph Search
▶ While q is not empty:
▶ v ← q.popFirst()
▶ For all neighbours u of v such that u ̸∈ q:
▶ Add u to q
By changing the behaviour of q, we recreate all the classical graph
search algorithms:
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
General Graph Search
▶ While q is not empty:
▶ v ← q.popFirst()
▶ For all neighbours u of v such that u ̸∈ q:
▶ Add u to q
By changing the behaviour of q, we recreate all the classical graph
search algorithms:
▶ If q is a stack, then the algorithm becomes DFS.
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
General Graph Search
▶ While q is not empty:
▶ v ← q.popFirst()
▶ For all neighbours u of v such that u ̸∈ q:
▶ Add u to q
By changing the behaviour of q, we recreate all the classical graph
search algorithms:
▶ If q is a stack, then the algorithm becomes DFS.
▶ If q is a standard FIFO queue, then the algorithm is BFS.
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
General Graph Search
▶ While q is not empty:
▶ v ← q.popFirst()
▶ For all neighbours u of v such that u ̸∈ q:
▶ Add u to q
By changing the behaviour of q, we recreate all the classical graph
search algorithms:
▶ If q is a stack, then the algorithm becomes DFS.
▶ If q is a standard FIFO queue, then the algorithm is BFS.
▶ If q is a priority queue, then the algorithm is Dijkstra.
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
General Graph Search
▶ While q is not empty:
▶ v ← q.popFirst()
▶ For all neighbours u of v such that u ̸∈ q:
▶ Add u to q
By changing the behaviour of q, we recreate all the classical graph
search algorithms:
▶ If q is a stack, then the algorithm becomes DFS.
▶ If q is a standard FIFO queue, then the algorithm is BFS.
▶ If q is a priority queue, then the algorithm is Dijkstra.
▶ If q is a priority queue with a heuristic, then the algorithm is
A*.
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
General Graph Search
▶ While q is not empty:
▶ v ← q.popFirst()
▶ For all neighbours u of v such that u ̸∈ q:
▶ Add u to q
By changing the behaviour of q, we recreate all the classical graph
search algorithms:
▶ If q is a stack, then the algorithm becomes DFS.
▶ If q is a standard FIFO queue, then the algorithm is BFS.
▶ If q is a priority queue, then the algorithm is Dijkstra.
▶ If q is a priority queue with a heuristic, then the algorithm is
A*.
Today we’re going to focus on Dijkstra.
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Dijkstra’s Algorithm
Given a graph G = (V , E ) where edges have nonnegative lengths,
and a source node s ∈ V , Dijkstra’s algorithm finds the shortest
path from s to every other node.
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Dijkstra’s Algorithm
Given a graph G = (V , E ) where edges have nonnegative lengths,
and a source node s ∈ V , Dijkstra’s algorithm finds the shortest
path from s to every other node.
A standard implementation of Dijkstra’s algorithm is the following:
▶ For all v ∈ V , dv ← ∞
▶ ds ← 0
▶ q.add(s)
▶ While q is not empty:
▶ v ← q.popFirst()
▶ For all neighbours u of v , such that dv + e(v , u) ≤ du :
▶ q.remove(u)
▶ du ← dv + e(v , u)
▶ q.add(u)
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Dijkstra’s Algorithm
Given a graph G = (V , E ) where edges have nonnegative lengths,
and a source node s ∈ V , Dijkstra’s algorithm finds the shortest
path from s to every other node.
A standard implementation of Dijkstra’s algorithm is the following:
▶ For all v ∈ V , dv ← ∞
▶ ds ← 0
▶ q.add(s)
▶ While q is not empty:
▶ v ← q.popFirst()
▶ For all neighbours u of v , such that dv + e(v , u) ≤ du :
▶ q.remove(u)
▶ du ← dv + e(v , u)
▶ q.add(u)
Runtime?
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Dijkstra’s Algorithm
Given a graph G = (V , E ) where edges have nonnegative lengths,
and a source node s ∈ V , Dijkstra’s algorithm finds the shortest
path from s to every other node.
A standard implementation of Dijkstra’s algorithm is the following:
▶ For all v ∈ V , dv ← ∞
▶ ds ← 0
▶ q.add(s)
▶ While q is not empty:
▶ v ← q.popFirst()
▶ For all neighbours u of v , such that dv + e(v , u) ≤ du :
▶ q.remove(u)
▶ du ← dv + e(v , u)
▶ q.add(u)
Runtime? O(|E | + |V | log |V |)
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Dijkstra’s Algorithm
Given a graph G = (V , E ) where edges have nonnegative lengths,
and a source node s ∈ V , Dijkstra’s algorithm finds the shortest
path from s to every other node.
A standard implementation of Dijkstra’s algorithm is the following:
▶ For all v ∈ V , dv ← ∞
▶ ds ← 0
▶ q.add(s)
▶ While q is not empty:
▶ v ← q.popFirst()
▶ For all neighbours u of v , such that dv + e(v , u) ≤ du :
▶ q.remove(u)
▶ du ← dv + e(v , u)
▶ q.add(u)
Runtime? O(|E | + |V | log |V |)
We can also adapt the algorithm to store the shortest path itself.
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Bellman-Ford
In the case when the graph may have negative edges, we must use
the Bellman-Ford algorithm:
▶ For all v ∈ V , dv ← ∞
▶ ds ← 0
▶ For t ∈ {1, . . . , |V |}:
▶ For all edges (v , u):
▶ du ← min{du , dv + e(v , u)}
▶ If there is an edge (v , u) such that dv + e(v , u) < du :
▶ Throw NEGATIVE CYCLE FOUND
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Bellman-Ford
In the case when the graph may have negative edges, we must use
the Bellman-Ford algorithm:
▶ For all v ∈ V , dv ← ∞
▶ ds ← 0
▶ For t ∈ {1, . . . , |V |}:
▶ For all edges (v , u):
▶ du ← min{du , dv + e(v , u)}
▶ If there is an edge (v , u) such that dv + e(v , u) < du :
▶ Throw NEGATIVE CYCLE FOUND
Runtime?
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Bellman-Ford
In the case when the graph may have negative edges, we must use
the Bellman-Ford algorithm:
▶ For all v ∈ V , dv ← ∞
▶ ds ← 0
▶ For t ∈ {1, . . . , |V |}:
▶ For all edges (v , u):
▶ du ← min{du , dv + e(v , u)}
▶ If there is an edge (v , u) such that dv + e(v , u) < du :
▶ Throw NEGATIVE CYCLE FOUND
Runtime? O(|E | · |V |)
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Bellman-Ford
In the case when the graph may have negative edges, we must use
the Bellman-Ford algorithm:
▶ For all v ∈ V , dv ← ∞
▶ ds ← 0
▶ For t ∈ {1, . . . , |V |}:
▶ For all edges (v , u):
▶ du ← min{du , dv + e(v , u)}
▶ If there is an edge (v , u) such that dv + e(v , u) < du :
▶ Throw NEGATIVE CYCLE FOUND
Runtime? O(|E | · |V |)
One additional reason to use Bellman-Ford over Dijkstra is that it’s
much easier to implement.
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Floyd-Warshall
Lastly, suppose we want to find the shortest paths between each
pair of nodes in graph:
▶ For all v ∈ V , du,v ← ∞
▶ For all (u, v ) ∈ E , du,v ← e(u, v )
▶ For w ∈ {1, . . . , |V |}:
▶ For all pairs of nodes (u, v ):
▶ du,v ← min{du,v , du,w + dw ,v }
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Floyd-Warshall
Lastly, suppose we want to find the shortest paths between each
pair of nodes in graph:
▶ For all v ∈ V , du,v ← ∞
▶ For all (u, v ) ∈ E , du,v ← e(u, v )
▶ For w ∈ {1, . . . , |V |}:
▶ For all pairs of nodes (u, v ):
▶ du,v ← min{du,v , du,w + dw ,v }
Runtime?
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Floyd-Warshall
Lastly, suppose we want to find the shortest paths between each
pair of nodes in graph:
▶ For all v ∈ V , du,v ← ∞
▶ For all (u, v ) ∈ E , du,v ← e(u, v )
▶ For w ∈ {1, . . . , |V |}:
▶ For all pairs of nodes (u, v ):
▶ du,v ← min{du,v , du,w + dw ,v }
Runtime? O(|V |3 )
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Floyd-Warshall
Lastly, suppose we want to find the shortest paths between each
pair of nodes in graph:
▶ For all v ∈ V , du,v ← ∞
▶ For all (u, v ) ∈ E , du,v ← e(u, v )
▶ For w ∈ {1, . . . , |V |}:
▶ For all pairs of nodes (u, v ):
▶ du,v ← min{du,v , du,w + dw ,v }
Runtime? O(|V |3 )
Again, Floyd-Warshall is less efficient, but much easier to
implement than all-pairs Dijkstra.
. . . . . . . . . . . . . . . . . . . .
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
