Scribd
Upload
4 views2 pages

Dijkstra Algorithm Example

Uploaded by

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

Dijkstra Algorithm Example

Uploaded by

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

Dijkstra's Algorithm with Example

Dijkstra's Algorithm is used to find the shortest path from a starting node to all other nodes
in a weighted graph with non-negative weights.

Algorithm Steps
1. Initialize distances: start node = 0, others = ∞. Mark all nodes unvisited.
2. Select the unvisited node with the smallest distance.
3. Update distances for each unvisited neighbor: distance = current_distance +
edge_weight. Update if smaller.
4. Mark the node as visited.
5. Repeat until all nodes are visited.

Example Graph
Consider the graph below with vertices A, B, C, D, and E:

Edges:
A→B=4
A→C=2
B→C=5
B→D=1
C→E=8
D→E=3

Step-by-Step Execution
Step A B C D E

Start at A 0 ∞ ∞ ∞ ∞

Visit A (0) 0 4 2 ∞ ∞

Visit C (2) 0 4 2 ∞ 10

Visit B (4) 0 4 2 5 10

Visit D (5) 0 4 2 5 8

Visit E (8) 0 4 2 5 8

Final Shortest Distances from A


A→A=0

A→B=4

A→C=2
A→D=5

A→E=8

You might also like