Understanding the Problem
We are given a weighted graph and a starting node (source). Our goal is to find the shortest distance from this source to all other nodes in the graph.
In other words, for every node in the graph, we want to calculate the minimum possible sum of edge weights required to reach that node from the source.
This problem is a classic case of finding single-source shortest paths in graphs with non-negative weights, and Dijkstra’s Algorithm is an efficient way to solve it using a priority queue
.
Step-by-Step Solution with Example
Step 1: Choose an Example
Let's consider the following weighted graph with 5 nodes (0 to 4), and the edges:
0 --(2)--> 1
0 --(4)--> 2
1 --(1)--> 2
1 --(7)--> 3
2 --(3)--> 4
3 --(1)--> 4
We want to find the shortest distance from node 0
to all other nodes.
Step 2: Initialize the Distance Array
Create a distance[]
array and fill it with Infinity
to represent that we don’t yet know the shortest path. Set the distance of the source node to 0.
distance = [0, ∞, ∞, ∞, ∞]
Step 3: Use a Min-Heap (Priority Queue)
Use a priority queue (min-heap) to always pick the next node with the smallest known distance. Initially, insert the source node with distance 0:
priorityQueue = [(0, 0)] // (distance, node)
Step 4: Start the Main Loop
While the priority queue is not empty:
- Extract the node with the smallest distance.
- Explore all its neighbors.
- If a shorter path to a neighbor is found, update the distance and insert it into the queue.
Step 5: Trace the Execution for Our Example
- Start with node 0, distance 0.
- Check edges: (0 → 1, weight 2), (0 → 2, weight 4)
- Update:
distance[1] = 2
, distance[2] = 4
- Queue: [(2,1), (4,2)]
- Next node: 1, distance 2
- Check edges: (1 → 2, weight 1) →
2 + 1 = 3
is better than current 4, update distance[2] = 3
- Also (1 → 3, weight 7) →
distance[3] = 9
- Queue: [(3,2), (4,2), (9,3)]
- Next node: 2, distance 3
- Check edge (2 → 4, weight 3) →
distance[4] = 6
- Queue: [(4,2), (9,3), (6,4)]
- Next node: 4, distance 6 → Already the best.
- Check edge (4 → 3, weight 1) →
6 + 1 = 7
is better than 9 → update distance[3] = 7
Step 6: Final Distance Array
distance = [0, 2, 3, 7, 6]
This gives the shortest path from node 0 to every other node in the graph.
Edge Cases
- Disconnected Graph: If a node is not reachable from the source, its distance will remain
Infinity
.
- Zero Weight Edges: Dijkstra’s algorithm handles them correctly as long as weights are non-negative.
- Multiple Edges Between Nodes: Always consider the one with the minimum weight during edge relaxation.
- Self-loops: They can be ignored unless required for the specific application.
Finally
Dijkstra’s Algorithm is a powerful tool for finding the shortest paths in a graph with non-negative weights. Using a priority queue helps efficiently expand the closest node at every step. Always remember to initialize distances properly and carefully update them when a shorter path is found. This algorithm is widely used in routing, pathfinding, and network optimization problems.
Comments
Loading comments...