Michael Ghoorchian

Dijkstra's algorithm ;
Shortest Path First
(SPF)
 Edsger W. Dijkstra (1930-2002)

• Dutch Computer Scientist

• Received Turing Award for
contribution to developing
programming languages.

Contributed to :
• Shortest path-algorithm, also known
as Dijkstra's algorithm;
• Reverse Polish Notation and related
www.math.bas.bg/.../EWDwww.jpg
Shunting yard algorithm; t
• THE multiprogramming system;
• Banker's algorithm;
• Self-stabilization – an alternative way
to ensure the reliability of the system.
 Dijkestra’s Algorithm
or Shortest path First

Dijkstra's algorithm is used in SPF, Shortest Path

First, which is used in the routing protocol OSPF,
Open Shortest Path First

Routing :
A protocol that specifies how routers communicate
with each other, disseminating information that
enables them to select routes between any two
nodes
on a computer network.
Shortest Path Algorithm
:
This algorithm has been used in GPS
navigating systems.

For a given source vertex (node) in the graph,

the algorithm can be used to find shortest
path from a single starting vertex to a single
destination vertex.

For example, if the vertices of the graph

represent cities and edge path costs represent
www.criticalblue.com
driving distances between pairs of cities
connected by a direct road, Dijkstra's
algorithm can be used to find the shortest
route between one city (a) and destination
city (b).
Shortest Path First (SPF)
Algorithm :
• This algorithm is widely used in routing protocol systems

• It is also called the single-source shortest path problem , in

which the shortest paths from a single source (vertex) to all
other vertices has to be found.

• In the next example; for a given source vertex (node) in the

graph, the algorithm finds the path with the shortest path
between that vertex and every other vertex. A Java applet
has been used to show the process step by step.
 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, s);
Initialize(G, s);
SS:=
:=;;
QQ:=:=V[G];
V[G];
while
whileQQdo do
uu:= Extract-Min(Q);
:= Extract-Min(Q);
SS:=:=SS{u};
{u};
for
foreach
eachvvAdj[u]
Adj[u]do
do
Relax(u,
Relax(u,v,
v,w)
w)
od
od
od
od

Single-
source
Comp 122, Fall 2003 SPs - 6
Example
u v
1
 

10
9
2 3
s 0 4 6

5 7

 
2
x y

Single-
source
Comp 122, Fall 2003 SPs - 7
Example
u v
1
10 

10
9
2 3
s 0 4 6

5 7

5 
2
x y

Single-
source
Comp 122, Fall 2003 SPs - 8
Example
u v
1
8 14

10
9
2 3
s 0 4 6

5 7

5 7
2
x y

Single-
source
Comp 122, Fall 2003 SPs - 9
Example
u v
1
8 13

10
9
2 3
s 0 4 6

5 7

5 7
2
x y

Single-
source
SPs -
Comp 122, Fall 2003 10
Example
u v
1
8 9

10
9
2 3
s 0 4 6

5 7

5 7
2
x y

Single-
source
SPs -
Comp 122, Fall 2003 11
Example
u v
1
8 9

10
9
2 3
s 0 4 6

5 7

5 7
2
x y

Single-
source
SPs -
Comp 122, Fall 2003 12
 Example of shortest path first (SPF) in
routing :

Red arrows point to nodes reachable from the start node a .

The distance to: b=4, d=1. Node d has the minimum distance.
Any other path to d visits another red node, and will be longer than 1.
On the next step , node d will be colored orange to indicate 1 is the length of the
shortest path to d.

 Java Applet Copyright Carla Laffra of Pace University ; http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra

 STEP
2
Red arrows point to nodes reachable from nodes that already have a final distance.
The distance to: b=4, e=33, g=23. Node b has the minimum distance.
Any other path to b visits another red node, and will be longer than 4.
On the next step, node b will be colored orange to indicate 4 is the length of the
shortest path to b.
 STEP
3
Red arrows point to nodes reachable from nodes that already have a final distance.
The distance to: c=6, e=16, g=23. Notice that the distance to e, has changed!
Node c has the minimum distance.
There are no other arrows coming in to c.
On the next step, node c will be colored orange to indicate 6 is the length of the
shortest path to c.
 STEP
4
Red arrows point to nodes reachable from nodes that already have a final distance.
The distance to: e=16, f=80, g=23, j=18. Node e has the minimum distance.
There are no other arrows coming in to e.
On the next step , e will be colored orange to indicate 16 is the length of the shortest
path to e.
 STEP
5
Red arrows point to nodes reachable from nodes that already have a final distance.
The distance to: f=80, g=23, h=49, j=18. Node j has the minimum distance.
Any other path to j visits another red node, and will be longer than 18.
Node j will be colored orange to indicate 18 is the length of the shortest path to j.
 STEP
6
Red arrows point to nodes reachable from nodes that already have a final distance.
The distance to: f=26, g=23, h=49. Notice that the distance to f, has changed!
Node g has the minimum distance.
Any other path to g visits another red node, and will be longer than 23.
Node g will be colored orange to indicate 23 is the length of the shortest path to g.
 STEP
7
Step 7: Red arrows point to nodes reachable from nodes that already have a final
distance.
The distance to: f=26, h=33. Notice that the distance to h, has changed!
Node f has the minimum distance.
Any other path to f visits another red node, and will be longer than 26.
Node f will be colored orange to indicate 26 is the length of the shortest path to f.
 STEP
8
Step 8: Red arrows point to nodes reachable from nodes that already have a final
distance.
The distance to: h=33, i=37. Node h has the minimum distance.
Any other path to h visits another red node, and will be longer than 33.
Node h will be colored orange to indicate 33 is the length of the shortest path to h.
 Last
step

Step 9: Red arrows point to nodes reachable from nodes that already have a final
distance.
The distance to: i=37. There are no other arrows coming in to i.
Node i will be colored orange to indicate 37 is the length of the shortest path to i.
Algorithm has finished, follow orange arrows from start node to any node to get
the shortest path to the node. The length of the path is written in the node.
 Does Dijkstra’s Algorithm works
everywhere ?

While it finds the shortest

path with lower running time
, It does not work with
negative weight of edges in
some networks.

In this case, Bellman-Ford

algorithm can be used which
is very similar to Dijkstra's
algorithm, but instead of
selecting the minimum-
weight node not yet
processed to relax, it simply
relaxes all the edges, and
Reference :
 Introduction to Algorithms by Cormen, Leiserson and
Rivest (MIT Press/McGraw-Hill 1994, ISBN 0-262-
03141-8 (MIT Press) and ISBN 0-07-013143-0
(McGraw-Hill).
 http://en.wikipedia.org/wiki/BellmanFord_algorithm
 http://en.wikipedia.org/wiki/Dijkstra_algorithm
 www.Criticalblue.com
 http://www.cs.mcgill.ca/~cs251/OldCourses/1997/
topic29/
 Introduction to Algorithms by Cormen, Leiserson and
Rivest (MIT Press/McGraw-Hill 1994, ISBN 0-262-
03141-8 (MIT Press) and ISBN 0-07-013143-0
(McGraw-Hill).