21CSC201J
DATA STRUCTURES AND
ALGORITHMS
Dijkstra’s Algorithm
UNIT 5
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.
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
Dijkstra's algorithm
Procedure
• It uses greedy technique.
• It proceeds in stages.
• It selects a vertex v, which has the smallest dv among all the unknown
vertices and declares the shortest path from s to v is known.
• The remainder consists of updating the value of dw.
• We should dw = dv + Cv, w, if the new value for dw would an improvement.
❖ Dijkstra’s algorithm can be implemented using list with a time complexity of
O(v2).
❖ When a binary heap is used for implementation then time complexity can be
reduced to O(E log V).
DIJKSTRA’S ALGORITHM- Example
v Known dv pv
V1 1 0 0
V2 0 ∞ 0
V3 0 ∞ 0
V4 0 ∞ 0
V1 is taken as source V5 0 ∞ 0
V6 0 ∞ 0
V7 0 ∞ 0
DIJKSTRA’S ALGORITHM-Example
v Known dv pv
V1 1 0 0
V2 0 2 V1
V3 0 ∞ 0
V4 0 1 V1
V5 0 ∞ 0
V6 0 ∞ 0
2. Now V1 is known vertex, marked as 1. Its adjacent vertices are v2, v4, pv and dv
V7 0 ∞ 0
values are updated.
T[v2].dist = Min(T[v2].dist,T[v1].dist + Cv1, v2)=Min(α, 0+2)=2
T[v4].dist = Min(T[v4].dist,T[v1].dist + Cv1, v4)=Min(α, 0+1)=1
DIJKSTRA’S ALGORITHM- Example
• 3. Select the vertex with minimum distance away v2 and v4 . v4 is marked as known vertex. Its adjacent vertices are
v3, v5, v6 and v7 .
• T[v3]. dist = Min (T[v3].dist, T[v4].dist + Cv4, v3) = Min (α , 1+2) = 3
•
• T[v5]. dist = Min (T[v5].dist, T[v4].dist + Cv4, v5) = Min (α , 1+2) = 3
•
• T[v6]. dist = Min (T[v6].dist, T[v4].dist + Cv4, v6) = Min (α , 1+8) = 9
•
• T[v7]. dist = Min (T[v7].dist, T[v4].dist + Cv4, v7) = Min (α , 1+4) = 5
DIJKSTRA’S ALGORITHM- Example
• 4. Select the vertex which is shortest distance from source v1. v2 is smallest one. v2 is marked
as known vertex. Its adjacent vertices are v4 ad v5. The distance from v1 to v4 and v5 through
v2 is more comparing with previous value of dv. No change in dv and pv value.
v Known dv pv
V1 1 0 0
V2 1 2 V1
V3 0 3 V4
V4 1 1 V1
V5 0 3 V4
V6 0 9 V4
V7 0 5 V4
DIJKSTRA’S ALGORITHM- Example
• 5. Select the smallest vertex from source. v3 and v5 are smallest one. Adjacent vertices for v3 is v1 and v6. v1 is source
• there is no change in dv and pv
• T[v6]. dist = Min (T[v6].dist, T[v3].dist + Cv3, v6) = Min (9 , 3+5) = 8
• dv and pv values are updated. Adjacent vertices for v5 is v7. No change in dv and pv value.
DIJKSTRA’S ALGORITHM- Example
• 6. Next smallest vertex v7. Its adjacent vertex is v6. T[v6]. dist = Min (T[v6].dist, T[v7].dist +
Cv7, v6) = Min (8 , 5+1) = 6
• dv and pv values are updated.
v Known dv pv
V1 1 0 0
V2 1 2 V1
V3 1 3 V4
V4 1 1 V1
V5 1 3 V4
V6 0 6 V7
V7 1 5 V4
DIJKSTRA’S ALGORITHM- Example
• 7. The last vertex v6 is declared as known. No adjacent vertices for v6. No updation in the table.
• The shortest distance from source v1 to all vertices. v1 -> v2 = 2
• v1 -> v3 = 3 v1 -> v4 = 1 v1 -> v5 = 3 v1 -> v6 = 6 v1 -> v7 = 5
• Algorithm Analysis
•
• Time complexity of this algorithm
•
• O(|E| + |V|2 ) = O(|V|2 )
Routine for prim’s Algorithm
void Dijkstra(Table T)
{
Vertex v, w; for( ; ;)
{
v = smallest unknown distance vertex;
if( v = = NotAVertex) break;
T[v]. kown = True;
for each w adjacent to v if(!T[w].known)
if(T[v].Dist + Cvw < T[w]. Dist)
{/* update w*/
Decrease(T[w]. Dist to T[v].Dist + Cvw);
T[w]. path = v;
}} }
Exercise
Using Dijkstra’s Algorithm, find the shortest distance from source
vertex ‘S’ to remaining vertices in the following graph
Review Questions
1. Dijkstra’s Algorithm is used to solve _____________ problems.
2. ___________is the most commonly used data structure for
implementing Dijkstra’s Algorithm.
3. __________ is the time complexity of Dijkstra's algorithm.
4. Dijkstra’s Algorithm cannot be applied on ______________
graph.
5. Dijkstra’s Algorithm is based on _______________ approach.
Thank you
