In the world of computer science and graph theory, Dijkstra’s Algorithm is one of the most famous and widely used algorithms to find the shortest path between nodes in a graph. Dijkstra’s algorithm, given by a brilliant Dutch computer scientist and software engineer Dr. Edsger Dijkstra in 1959. Dijkstra’s algorithm is a greedy algorithm that solves the single-source shortest path problem for a directed and undirected graph that has non-negative edge weight.
Dijkstra’s Algorithm works for both directed and undirected graphs, as long as all edge weights are non-negative.
How It Works for Both Graphs?
- Undirected Graph: Each edge is treated as bidirectional. For example, if there is an edge between A and B with weight 2, the algorithm considers you can go from A → B and from B → A, both with weight 2.
- Directed Graph: Each edge has a specific direction. If there’s an edge from A → B with weight 2, but no edge from B → A, then you can only travel from A to B, not the other way around.
Statement
For Graph G = (V,E)
w (u, v) ≥ 0 for each edge (u, v) ∈ E.
Means: “In the graph G, for every connection (edge) between nodes u and v, the weight (or cost) must be zero or positive.”
Explanation:
1. G = (V, E)
This is the mathematical representation of a graph:
- V = the set of vertices (nodes)
- E = the set of edges (connections between nodes)
So, G = (V,E) means the graph is made up of:
- A list of nodes (like cities or people), and
- A list of edges (like roads or relationships) that connect those nodes.
2. w(u, v)
This is the weight function.
It gives the weight or cost of traveling from node u to node v via edge (u, v).
For example:
- If
u = Aandv = Bandw(A, B) = 5, it means there’s a path from A to B with a cost/weight of 5.
3. w(u, v) ≥ 0
This means the weight of every edge is non-negative.
- It cannot be negative (i.e., no edge can have a cost like -3).
- It can be zero or positive (i.e., 0, 1, 5, 100, etc.).
4. (u, v) ∈ E
This means the condition applies to all edges in the graph.
Limitation of Dijkstra’s Algorithm?
Dijkstra’s Algorithm only works when all edge weights are non-negative. If even one edge has a negative weight, Dijkstra’s logic can fail to find the correct shortest path. That’s why this condition w(u, v) ≥ 0 is a requirement for applying Dijkstra’s Algorithm.
Example of Dijkstra’s Algorithm
Problem
We want to find the shortest distance from one source node to all other nodes in a graph with non-negative weights.
Example Graph
- 5 cities (nodes): A (0), B (1), C (2), D (3), E (4)
- Roads (edges with distances):
- A → B = 4
- A → C = 2
- B → C = 5
- B → D = 10
- C → E = 3
- E → D = 4
Goal
Find the shortest distance from A to every other city using Dijkstra’s Algorithm.
Steps to Find the shortest Distance
- Start at A (source):
- Distance to itself = 0.
- Distances to others = ∞ (unknown yet).
A=0, B=∞, C=∞, D=∞, E=∞- From A, check neighbors:
- A → B = 4 → update B = 4.
- A → C = 2 → update C = 2.
A=0, B=4, C=2, D=∞, E=∞Pick the smallest unvisited: C (2).
- From C, check neighbors:
- C → E = 3 → A→C (2) + C→E (3) = 5 → update E = 5.
- C → B = 5 → A→C (2) + C→B (5) = 7 (but current B=4, so no update).
A=0, B=4, C=2, D=∞, E=5Next smallest unvisited: B (4).
- From B, check neighbors:
- B → D = 10 → A→B (4) + 10 = 14 → update D = 14.
- B → C = 5, but C is already shorter (2).
A=0, B=4, C=2, D=14, E=5Next smallest unvisited: E (5).
- From E, check neighbors:
- E → D = 4 → A→E (5) + 4 = 9 → update D = 9 (better than 14).
A=0, B=4, C=2, D=9, E=5Next smallest unvisited: D (9).
- From D, check neighbors:
- Nothing shorter is found.
Final Shortest Distances from A
- A → A = 0
- A → B = 4
- A → C = 2
- A → D = 9
- A → E = 5
Dijkstra’s Algorithm
- Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest-path tree, i.e., whose minimum distance from the source is calculated and finalized. Initially, this set is empty.
- Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
- While sptSet doesn’t include all vertices
- Pick a vertex u which is not there in sptSet and has a minimum distance value.
- Include u to sptSet.
- Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if the sum of a distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.
How Dijkstra’s Algorithm Works
Here’s a step-by-step explanation:
- Start at the source node and set its distance to
0. Set all other nodes’ distances to infinity (∞). - Maintain a priority queue (or min-heap) of unvisited nodes, prioritized by the smallest known distance.
- At each step:
- Pick the node with the smallest known distance.
- For each unvisited neighbor:
- Calculate new distance = current node’s distance + edge weight.
- If this new distance is less than the previously recorded distance, update it.
- Mark the current node as visited.
- Repeat until all nodes are visited or the shortest path to the destination is found.
Pseudocode of Dijkstra’s Algorithm
function Dijkstra(Graph, source):
create distance[] and set all values to infinity
distance[source] = 0
create a min-priority queue and add source
while queue is not empty:
current = extract_min(queue)
for neighbor in current.neighbors:
temp_dist = distance[current] + weight(current, neighbor)
if temp_dist < distance[neighbor]:
distance[neighbor] = temp_dist
update priority queue with new distance
return distance[]Optimized Version: Using Priority Queue
Problem with the normal approach
- In the regular Dijkstra, to pick the next closest node, we look at all unvisited nodes and find the one with the smallest distance.
- If there are many nodes, this takes a lot of time (O(V²)).
Using a PriorityQueue greatly improves performance (from O(V²) to O((V+E) log V)).
How Priority Queue helps
- A Priority Queue is like a “smart waiting line” where the node with the smallest distance always comes out first.
- This means we don’t need to scan all nodes every time to find the closest one.
- When we update a neighbor’s distance, we add it to the queue. The queue automatically keeps it in the right order.
Lets see an example to understand Dijkstra’s Algorithm
Below is a directed weighted graph. We will find shortest path between all the vertices using Dijkstra’a Algorithm.
Java Code to Implement Dijkstra’s Algorithm
import java.util.*;
public class DijkstraExample {
static class Edge {
int target, weight;
public Edge(int target, int weight) {
this.target = target;
this.weight = weight;
}
}
public static void dijkstra(List<List<Edge>> graph, int source) {
int n = graph.size();
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{source, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int node = current[0];
int currentDist = current[1];
for (Edge edge : graph.get(node)) {
int neighbor = edge.target;
int newDist = currentDist + edge.weight;
if (newDist < dist[neighbor]) {
dist[neighbor] = newDist;
pq.offer(new int[]{neighbor, newDist});
}
}
}
for (int i = 0; i < n; i++) {
System.out.println("Distance from " + source + " to " + i + " is " + dist[i]);
}
}
public static void main(String[] args) {
int n = 5; // number of nodes
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
// add edges: graph.get(u).add(new Edge(v, weight));
graph.get(0).add(new Edge(1, 1)); // A to B
graph.get(0).add(new Edge(3, 4)); // A to D
graph.get(1).add(new Edge(2, 3)); // B to C
graph.get(1).add(new Edge(4, 2)); // B to E
graph.get(3).add(new Edge(4, 1)); // D to E
dijkstra(graph, 0); // source is node 0 (A)
}
}Time and Space Complexity of Dijkstra’s Algorithm
| Implementation | Time Complexity |
|---|---|
| Naive (Simple array) | O(V²) |
| Using Priority Queue (Min-Heap) | O((V + E) log V) |
| Implementation | Space Complexity |
|---|---|
| Naive (Simple array) | O(V) |
| Using Priority Queue (Min-Heap) | O(V + E) |
When to Use Dijkstra’s Algorithm
Use Dijkstra’s Algorithm when:
- You want to find the shortest path from a single source to all other nodes.
- Your graph contains non-negative weights.
- The graph is sparse or large, and you want efficiency.
Real-Life Applications of Dijkstra’s Algorithm
- GPS systems (Google Maps, Uber)
- To find the shortest path between source and destination
- Network packet routing (OSPF in networking)
- AI in games for pathfinding (e.g., enemy chase logic)
- In social networking applications to map the connections and information
- In networking to route the data
Disadvantage of Dijkstra’s Algorithm
- It follows the blind search, so wastes a lot of time to give the desired output.
- It Negative edges value cannot be handled by it.
- We need to keep track of vertices that have been visited.
Comparison with Other Algorithms
| Algorithm | Handles Negative Weights | Complexity | Best Use Case |
|---|---|---|---|
| Dijkstra | No | O((V + E) log V) | Fastest on non-negative graphs |
| Bellman-Ford | Yes | O(V * E) | Graphs with negative weights |
| A* | No (unless heuristics handle it) | Depends on heuristic | Pathfinding with prediction |
| Floyd-Warshall | Yes | O(V³) | All-pairs shortest paths |
FAQs and Interview Questions
- Can Dijkstra’s Algorithm be used for negative weights?
No, use Bellman-Ford for that. - Why use PriorityQueue in Dijkstra?
To optimize the selection of the minimum distance node. - Can Dijkstra find all shortest paths from one node?
Yes, to all nodes with non-negative weights. - What is the time complexity with a min-heap?
O((V + E) log V)