CS 316: ALGORITHMS
Graph
Single-Source Shortest Path
Assoc. Prof. Ensaf Hussein
Department Of Computer Science
01/20/2024
SHORTEST PATH
Generalize distance to weighted setting
Digraph G = (V,E) with weight function W: E →R (assigning
real values to edges)
Weight of path p = v1 →v2 →… →vk is
k 1
w( p) w(vi , vi 1 )
i 1
Shortest path = a path of the minimum weight
Applications
• static/dynamic network routing
• robot motion planning
• map/route generation in traffic 2
RELAXATION
Initialize(G,
Initialize(G,s)s)
for eachvvV[G]
foreach V[G]do
do
d[v]
d[v]:=:=;
;
[v]
[v]:=:=NIL
NIL
End
Endfor;
for;
d[s]
d[s]:=
:=00
Relax(u,
Relax(u,v,v,w)w)
ififd[v]
d[v]>>d[u]
d[u]++w(u,
w(u,v)
v)
then
then
d[v]
d[v]:=
:=d[u]
d[u]++w(u,
w(u,
v);
v); 3
[v]
[v]:=
:=uu
End
Endifif
DIJKSTRA'S ALGORITHM
Non-negative edge weights
Greedy, similar to Prim's algorithm for MST
Like breadth-first search (if all weights = 1, one can simply use BFS)
Use Q, a priority queue ADT keyed by v.d() (BFS used FIFO queue,
here we use a PQ, which is re-organized whenever some d decreases)
Basic idea
• maintain a set S of solved vertices
• at each step select "closest" vertex u, add it to S, and relax all
edges from u
4
DIJKSTRA’S ALGORITHM
Assumes no negative-weight edges.
Maintains a set S of vertices whose SP from s has been determined.
Repeatedly selects u in V–S with minimum SP estimate (greedy choice).
Store V–S in priority queue Q.
Initialize(G,
Initialize(G,s);
s);
:=;
SS:= ;
QQ:=:=V[G];
V[G];
whileQQ
while dodo
uu:=
:=Extract-Min(Q);
Extract-Min(Q);
:=SS
SS:= {u};
{u};
for eachvvAdj[u]
foreach Adj[u]do
do
Relax(u,
Relax(u,v,v,w)
w)
End
Endfor
for
End
Endwhile
while
EXAMPLE
u v
1
10
9
2 3
s 0 4 6
5 7
2
x y
EXAMPLE
u v
1
10
10
9
2 3
s 0 4 6
5 7
5
2
x y
EXAMPLE
u v
1
8 14
10
9
2 3
s 0 4 6
5 7
5 7
2
x y
EXAMPLE
u v
1
8 13
10
9
2 3
s 0 4 6
5 7
5 7
2
x y
EXAMPLE
u v
1
8 9
10
9
2 3
s 0 4 6
5 7
5 7
2
x y
EXAMPLE
u v
1
8 9
10
9
2 3
s 0 4 6
5 7
5 7
2
x y
DIJKSTRA’S RUNNING TIME
Extract-Min executed |V| time
Decrease-Key executed |E| timeincorrect
Time = |V| TExtract-Min + |E| TDecrease-Key
T depends on different Q implementations
Time Complexity is
(|V|-1)|E| + |E|
= O(VE)
Q T(Extract T(Decrease- Total
-Min) Key)
array O(V) O(1) O(V 2)
binary heap O(lg V) O(lg V) O(E lg V) 12
SHORTEST PATHS IN DAG
(DIRECTED ACYCLIC GRAPH)
Recall that a Directed Acyclic Graph (DAG) is a graph with
directed edges and no cycles. By definition this means all
trees are automatically DAGs since they do not contain
cycles.
Topologically
Topologicallysort
sortvertices
verticesin
inG;
G;
Initialize(G,
Initialize(G,s);
s);
for
foreach
eachuuin
inV[G]
V[G](in(inorder)
order)do
do
for
foreach
eachvvininAdj[u]
Adj[u]dodo
Relax(u,
Relax(u,v,v,w)
w)
End
Endfor
for
End
Endforfor
EXAMPLE
The Single Source Shortest Path(SSSP) problem can be
solved efficiently on a DAF in O(V+E) time. This is due to
the fact that the nodes can be ordered in a topological
ordering via topsort and processed sequentially.
6 1
r s t u v w
5 0
2
7
–1
–2
4
3
2
EXAMPLE
6 1
r s t u v w
5 0
2
7
–1
–2
4
3
2
EXAMPLE
6 1
r s t u v w
5 0
2 2
7 6
–1
–2
4
3
2
EXAMPLE
6 1
r s t u v w
5 0
2 2
7 6
–1 6
–2 4
4
3
2
EXAMPLE
6 1
r s t u v w
5 0
2 2
7 6
–1 5
–2 4
4
3
2
EXAMPLE
6 1
r s t u v w
5 0
2 2
7 6
–1 5
–2 3
4
3
2
EXAMPLE
6 1
r s t u v w
5 0
2 2
7 6
–1 5
–2 3
4
3
2
Time Complexity is Θ(V + E) time
BELLMAN-FORD ALGORITHM
Can have negative-weight edges. Will “detect” reachable negative-weight
cycles.
Initialize(G,
Initialize(G,s); s);
for
forii:= :=11toto| |V[G]|
V[G]|–1 –1do
do
for
foreach
each(u, (u,v)
v)in
inE[G]
E[G]dodo Time Complexity is
Relax(u,
Relax(u,v,v,w) w) (|V|-1)|E| + |E| = O(VE).
End
Endfor for Time Complexity is
End
Endfor; for; (|V|-1)|E| + |E|
for
foreach
each(u,(u,v)v)ininE[G]
E[G]=do
doO(VE)
ififd[v]
d[v]>>d[u]d[u]++w(u,
w(u,v)v)then
then
return
returnfalsefalse
End
Endifif
End
Endfor; for;
return
returntrue true
EXAMPLE
u v
5
–2
6 –3
8
z 0 7
–4
7 2
9
x y
EXAMPLE
u v
5
6
–2
6 –3
8
z 0 7
–4
7 2
7
9
x y
EXAMPLE
u v
5
6 4
–2
6 –3
8
z 0 7
–4
7 2
7 2
9
x y
EXAMPLE
u v
5
2 4
–2
6 –3
8
z 0 7
–4
7 2
7 2
9
x y
EXAMPLE
u v
5
2 4
–2
6 –3
8
z 0 7
–4
7 2
7 2
9
x y
EXAMPLE
u v
5
2 4
–2
6 –3
8
z 0 7
–4
7 2
7 -2
9
x y
ANOTHER LOOK
Note: This is essentially dynamic programming.
Let d(i, j) = cost of the shortest path from s to i that is at most j hops.
0 if i = s j = 0
d(i, j) = if i s j = 0
min({d(k, j–1) + w(k, i): i Adj(k)}
{d(i, j–1)}) if j > 0
i
z u v x y
1 2 3 4 5
j 0 0
1 0 6 7
2 0 6 4 7 2
3 0 2 4 7 2
4 0 2 4 7 –2
BELLMAN-FORD ALGORITHM
Dijkstra’s doesn’t work when there are negative edges:
• Intuition – we can not be greedy any more on the
assumption that the lengths of paths will only increase in
the future
Bellman-Ford algorithm detects negative cycles (returns
false) or returns the shortest path-tree
29
