GraphProblem 12 of 43
Dijkstra algo
Problem Statement
Given a weighted graph with V vertices and E edges, and a source vertex, find the shortest distance from the source to all other vertices. All edge weights are non-negative.
Example:
- Input:
V = 5, src = 0, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]] - Output:
[0, 3, 1, 4, 7](shortest distances from vertex 0)
Noob-Friendly Explanation
Imagine you're using Google Maps and want to find the shortest drive time from your home to every other location. Each road has a certain travel time (weight). Dijkstra's algorithm is like a smart explorer:
- Start at home (distance = 0).
- Look at all places you can reach directly. Pick the closest one.
- From there, see if you can find shorter routes to other places.
- Repeat until you've found the shortest route to everywhere.
The key idea: always process the closest unvisited place next, because you know you've already found the shortest path to it.
Approach 1: Brute Force (Simple Array)
Intuition
Maintain a distance array. In each round, find the unvisited vertex with the smallest distance, mark it visited, and update distances to its neighbors. This is the classic Dijkstra without a priority queue.
Algorithm
- Initialize all distances to infinity, source distance to 0.
- Repeat V times: a. Find the unvisited vertex with minimum distance. b. Mark it visited. c. Update distances of all its neighbors.
java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class DijkstraBruteForce {
public static int[] dijkstra(int V, int[][] edges, int src) {
// Build adjacency list: {neighbor, weight}
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
adj.get(edge[1]).add(new int[]{edge[0], edge[2]}); // undirected
}
int[] dist = new int[V];
boolean[] visited = new boolean[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 0; i < V; i++) {
// Find unvisited vertex with minimum distance
int u = -1;
for (int v = 0; v < V; v++) {
if (!visited[v] && (u == -1 || dist[v] < dist[u])) {
u = v;
}
}
if (dist[u] == Integer.MAX_VALUE) break;
visited[u] = true;
// Update neighbors
for (int[] neighbor : adj.get(u)) {
int v = neighbor[0], weight = neighbor[1];
if (!visited[v] && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
return dist;
}
public static void main(String[] args) {
int V = 5;
int[][] edges = {{0,1,4},{0,2,1},{2,1,2},{1,3,1},{2,3,5},{3,4,3}};
int[] result = dijkstra(V, edges, 0);
System.out.println(Arrays.toString(result)); // [0, 3, 1, 4, 7]
}
}Complexity Analysis
- Time Complexity: O(V^2) — for each of V iterations, we scan all V vertices to find the minimum.
- Space Complexity: O(V) — for the distance and visited arrays.
Approach 2: Optimal (Priority Queue / Min-Heap)
Intuition
Use a min-heap (priority queue) to always get the vertex with the smallest distance in O(log V) time instead of O(V). This dramatically speeds up the algorithm for sparse graphs.
Algorithm
- Initialize distances to infinity, source to 0.
- Add (0, source) to the priority queue.
- While the queue is not empty: a. Extract the vertex with the minimum distance. b. If already visited, skip. c. Mark visited and update distances to all neighbors. d. If a shorter path is found, add the neighbor to the queue.
java
import java.util.*;
public class DijkstraOptimal {
public static int[] dijkstra(int V, int[][] edges, int src) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
adj.get(edge[1]).add(new int[]{edge[0], edge[2]});
}
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// Min-heap: {distance, vertex}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.add(new int[]{0, src});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0], u = curr[1];
if (d > dist[u]) continue; // skip outdated entries
for (int[] neighbor : adj.get(u)) {
int v = neighbor[0], weight = neighbor[1];
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.add(new int[]{dist[v], v});
}
}
}
return dist;
}
public static void main(String[] args) {
int V = 5;
int[][] edges = {{0,1,4},{0,2,1},{2,1,2},{1,3,1},{2,3,5},{3,4,3}};
int[] result = dijkstra(V, edges, 0);
System.out.println(Arrays.toString(result)); // [0, 3, 1, 4, 7]
}
}Complexity Analysis
- Time Complexity: O((V + E) log V) — each vertex is extracted once from the heap (log V), and each edge is relaxed once.
- Space Complexity: O(V + E) — for the adjacency list and priority queue.