Dijkstra Algorithm

Course Name: Algorithm

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, AIUB

 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
Shunting yard algorithm; t
•THE multiprogramming system;
•Banker's algorithm;
Self-stabilization – an alternative way to
ensure the reliability of the system

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, AIUB

 Single Source Shortest Path Problem
The problem of finding shortest paths from a source vertex v to all other vertices in the
graph.

4 D

20
1 MIS 3
0 T

BUP AIUB
5

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, AIUB

 CONCEPT OF SHORTEST PATH

8
D
4
1

8
0 20
1 MIST
3
0

BUP AIU
5 B
0 5

8
8

• Which one is the suitable path for visiting from BUP to D?

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, AIUB

 CONCEPT OF SHORTEST PATH

25

8
D
4
810

8
20
10 MIST 3

BUP AIU
5 B
0 5

8
8

• Which one is the suitable path for visiting from Hall to D?

• HALL -> ACB-> MIST -> D

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, AIUB

 CONCEPT OF SHORTEST PATH
1 2

8
2 5
D
4
81

8
0 2
1 MIS 3
T 0 • This algorithm is known as
0
Dijkstra’s algorithm
BUP AIU
5 B
0 5

8
8

• Which one is the suitable path for visiting from BUP to D?

• HALL -> M12 -> MIST -> D

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST 6

 Dijkstra's Algorithm
Dijkstra's algorithm - is a solution to the single-source shortest path problem in
graph theory.

Works on both directed and undirected graphs. However, all edges must have
nonnegative weights.

Approach: Greedy

Input: Weighted graph G={E,V} and source vertex v∈V, such that all edge
weights are nonnegative

Output: Lengths of shortest paths (or the shortest paths themselves) from a given
source vertex v∈V to all other vertices

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

 Pseudo code
for all v ∈ V
do dist[v] ←∞ (set all distances
infinity)
visit[v] ← false (set all noted visit status to
false)

dist[s] ←0 (distance to sourc

vertex is zero)
S←∅ (S, the set of visi
vertices is initially empty)
for all v ∈ V–{s}
do u ← mindistance(dist,visit) (select the unvisited node with the min.
distance)
S←S∪{u} (add u to list of visited vertic
visit[u]← true
for all v ∈ unvisited neighbors[u]
do if dist[v] > dist[u] + w(u, v) (if new shortest path found)
then dist[v] ←dist[u] + w(u, v) (set new value of shortest path)
returnby:
Prepared distNuzhat Tabassum, Asst. Prof, Dept of CSE, MIST
 Dijkstra’s Simulation

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

 Dijkstra’s Simulation

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

 Dijkstra’s Simulation

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

 Dijkstra’s Simulation

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

 Dijkstra’s Simulation

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

 Dijkstra’s Simulation

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

 Dijkstra’s Simulation

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

 Dijkstra’s Simulation

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

 Dijkstra’s Simulation

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

 Dijkstra’s Simulation

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

 Application
Traffic Information Systems are most prominent use
- Mapping (Map Quest, Google Maps)
- Routing Systems

Prepared by: Nuzhat Tabassum, Asst. Prof, Dept of CSE, MIST

Thank You