Scribd
Upload
3 views4 pages

Dijkstra Algorithm ADA Explanation

Dijkstra's Algorithm is designed to find the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights, applicable in various fields such as routing and navigation. The algorithm operates by initializing distances, selecting the minimum distance vertex, relaxing edges, and updating distances until all vertices are processed. Its time complexity varies based on the data structure used, with options including Θ(V²) for a weight matrix and O(E log V) for an adjacency list with a min heap.

Uploaded by

lshree2
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views4 pages

Dijkstra Algorithm ADA Explanation

Dijkstra's Algorithm is designed to find the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights, applicable in various fields such as routing and navigation. The algorithm operates by initializing distances, selecting the minimum distance vertex, relaxing edges, and updating distances until all vertices are processed. Its time complexity varies based on the data structure used, with options including Θ(V²) for a weight matrix and O(E log V) for an adjacency list with a min heap.

Uploaded by

lshree2
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Dijkstra's Algorithm - ADA Screen Recording Notes

1. Why Dijkstra's Algorithm is Used


Dijkstra's Algorithm is used to find the shortest path from a single source vertex to all other vertices
in a weighted graph having non-negative edge weights. Applications include routing, transportation
planning, communication networks, robotics, social networks, and navigation systems.

2. Single Source Shortest Path Problem


Given a source vertex s in a weighted connected graph, determine the shortest paths from s to
every other vertex.

3. Working Principle
1. Start from the source vertex.
2. Assign distance 0 to source and infinity to all other vertices.
3. Select the unvisited vertex with minimum distance.
4. Relax all adjacent edges.
5. Update distances if a shorter path is found.
6. Mark the vertex as finalized.
7. Repeat until all vertices are processed.
4. Algorithm with Line-by-Line Explanation
Initialize(Q)
Creates an empty priority queue.

for every vertex v in V


d[v] = ∞, p[v] = null
Meaning: Initially shortest distance is unknown.

Insert(Q,v,d[v])
Insert all vertices into priority queue.

d[s] = 0
Distance from source to itself is zero.

Decrease(Q,s,d[s])
Update source priority to zero.

VT ← ∅
Tree vertices set is initially empty.

for i = 0 to |V|-1
Repeat until every vertex is processed.

u* ← DeleteMin(Q)
Choose vertex with minimum tentative distance.

VT ← VT ∪ {u*}
Add selected vertex into shortest path tree.

for every adjacent vertex u


Check all neighboring vertices.

if d[u*] + w(u*,u) < d[u]


Verify whether a shorter path exists.

d[u] ← d[u*] + w(u*,u)


Update shortest distance.

p[u] ← u*
Store predecessor vertex.

Decrease(Q,u,d[u])
Update priority queue.
5. Iteration Table for the Example in Notes
Graph edges:
a-b=3, a-d=7, b-d=2, b-c=4, d-c=5, d-e=4, c-e=6

Source Vertex = a
Iteration 0
Distance(a)=0
Distance(b)=3
Distance(d)=7
Distance(c)=∞
Distance(e)=∞
Selected Vertex = a

Iteration 1
Minimum vertex = b (3)
Update d via b = 3+2 = 5
Update c via b = 3+4 = 7
Distances: a=0, b=3, d=5, c=7, e=∞

Iteration 2
Minimum vertex = d (5)
Update e via d = 5+4 = 9
c through d = 5+5 =10 (not better than 7)
Distances: a=0, b=3, d=5, c=7, e=9

Iteration 3
Minimum vertex = c (7)
e through c = 7+6 =13 (not better than 9)
Distances unchanged.

Iteration 4
Minimum vertex = e (9)
Algorithm terminates.
6. Final Shortest Paths
a→b=3
a→b→d=5
a→b→c=7
a→b→d→e=9

Shortest Path Tree Edges:


(a,b), (b,d), (b,c), (d,e)

7. Time Complexity
Weight Matrix + Unordered Array : Θ(V²)
Adjacency List + Min Heap : O(E log V)

8. Applications
• Transportation planning
• Internet routing
• GPS navigation systems
• Robotics
• Social networks
• Airline scheduling

You might also like