Dijkstra’s Algorithm Using Priority Queue

You are given a weighted, undirected, and connected graph with V vertices represented using an adjacency list. Each entry adj[i] contains a list of lists, where each sublist contains two integers j and weight, representing an edge from vertex i to vertex j with a given weight.

Given a source vertex S, your task is to find the shortest distances from S to all other vertices using Dijkstra’s Algorithm and return them as a list.

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:

1. Extract the node with the smallest distance.
2. Explore all its neighbors.
3. 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.

1. Initialize dist[] with Infinity, set dist[S] = 0.
2. Create a priority queue (min-heap) and insert {0, S}.
3. While the queue is not empty:
1. Pop the vertex with the minimum distance from the queue.
2. For each adjacent vertex v of the current node:
1. If dist[u] + weight < dist[v], update dist[v] and add {dist[v], v} to the queue.
4. Return dist[] as the shortest distances from source S.