Understanding the Problem
We are given a weighted graph with non-negative edge weights, and our goal is to find the shortest paths from a source vertex to all other vertices. This is a classic single-source shortest path problem.
To solve it, we’ll use Dijkstra’s Algorithm, which is efficient and guarantees the shortest path when weights are non-negative. In this version, we will implement it using a set
data structure, which helps us quickly get the vertex with the current minimum tentative distance.
Step-by-Step Solution with Example
Step 1: Initialize Distance Array
Let’s consider a sample graph:
0 --1--> 1
0 --4--> 2
1 --2--> 2
1 --6--> 3
2 --3--> 3
The graph has 4 nodes (0 to 3) and weighted edges. We'll find the shortest path from node 0 to all others.
Start by initializing a distance[]
array with infinity for all nodes, except the source node (0), which will be 0:
distance[] = [0, ∞, ∞, ∞]
Step 2: Insert Source into Set
We use a set of pairs (distance, node)
. Start with:
set = {(0, 0)}
Step 3: Extract Node with Minimum Distance
Pick the node with the smallest distance from the set, which is (0, 0)
. Visit all its neighbors:
- To node 1: distance = 0 + 1 = 1 → Update and insert (1, 1)
- To node 2: distance = 0 + 4 = 4 → Update and insert (4, 2)
distance[] = [0, 1, 4, ∞]
set = {(1, 1), (4, 2)}
Step 4: Process Next Node
Pick (1, 1). Neighbors:
- To node 2: 1 + 2 = 3 → Better than 4, update (remove 4,2) and insert (3, 2)
- To node 3: 1 + 6 = 7 → Update and insert (7, 3)
distance[] = [0, 1, 3, 7]
set = {(3, 2), (7, 3)}
Step 5: Process Node 2
Pick (3, 2). Neighbors:
- To node 3: 3 + 3 = 6 → Better than 7, update (remove 7,3) and insert (6, 3)
distance[] = [0, 1, 3, 6]
set = {(6, 3)}
Step 6: Process Final Node
Pick (6, 3). No updates as all neighbors already have optimal distances. Done.
Edge Cases
- Disconnected Nodes: Some nodes may not be reachable. Their distances will remain infinity.
- Multiple Edges: If multiple edges exist between two nodes, consider the one with minimum weight.
- Self-loops: These don’t help in pathfinding and can be ignored.
- Negative Weights: Dijkstra’s algorithm does not work correctly with negative edge weights. Always validate input.
Finally
Dijkstra’s algorithm is a powerful and efficient method for solving shortest path problems in graphs with non-negative weights. By using a set
, we can maintain and access the node with the minimum tentative distance in logarithmic time, making the algorithm efficient for sparse graphs.
For dense graphs or when performance is critical, using a priority queue (min-heap) might be even faster. However, the set
-based approach remains intuitive and easy to implement.
Comments
Loading comments...