Shortest Path Algorithms
Shortest Path Problem
Given a weighted graph, find the path between two vertices with the minimum total edge weight. Different algorithms suit different scenarios:
| Algorithm | Graph Type | Time | Negative Weights? |
|---|---|---|---|
| BFS | Unweighted | O(V + E) | N/A |
| Dijkstra | Weighted, non-negative | O((V + E) log V) | No |
| Bellman-Ford | Weighted, any | O(V × E) | Yes |
| Floyd-Warshall | All pairs | O(V³) | Yes (no neg cycles) |
Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a greedy approach with a min-priority queue.
import java.util.*;
public class Dijkstra {
static int V;
static List<int[]>[] adj; // adj[u] = list of {v, weight}
@SuppressWarnings("unchecked")
static void buildGraph(int v) {
V = v;
adj = new ArrayList[v];
for (int i = 0; i < v; i++) adj[i] = new ArrayList<>();
}
static void addEdge(int u, int v, int w) {
adj[u].add(new int[]{v, w});
adj[v].add(new int[]{u, w}); // undirected
}
// Dijkstra — O((V + E) log V) with priority queue
static int[] dijkstra(int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// Min-heap: {distance, vertex}
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, src});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0], u = curr[1];
if (d > dist[u]) continue; // outdated entry
for (int[] edge : adj[u]) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}
}
}
return dist;
}
public static void main(String[] args) {
buildGraph(5);
addEdge(0, 1, 4); addEdge(0, 2, 1);
addEdge(2, 1, 2); addEdge(1, 3, 1);
addEdge(2, 3, 5); addEdge(3, 4, 3);
int[] dist = dijkstra(0);
System.out.println("Shortest distances from vertex 0:");
for (int i = 0; i < V; i++) {
System.out.println(" to " + i + ": " + dist[i]);
}
// to 0: 0, to 1: 3, to 2: 1, to 3: 4, to 4: 7
}
}import java.util.Arrays;
public class BellmanFord {
static int V, E;
static int[][] edges; // {u, v, weight}
// Bellman-Ford — O(V * E), handles negative weights
static int[] bellmanFord(int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// Relax all edges V-1 times
for (int i = 0; i < V - 1; i++) {
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// Check for negative weight cycles
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
System.out.println("Negative weight cycle detected!");
return null;
}
}
return dist;
}
public static void main(String[] args) {
V = 5; E = 8;
edges = new int[][]{
{0,1,-1},{0,2,4},{1,2,3},{1,3,2},{1,4,2},
{3,2,5},{3,1,1},{4,3,-3}
};
int[] dist = bellmanFord(0);
if (dist != null) {
System.out.println("Shortest distances from 0:");
for (int i = 0; i < V; i++)
System.out.println(" to " + i + ": " + dist[i]);
}
// to 0:0, to 1:-1, to 2:2, to 3:-2, to 4:1
}
}Floyd-Warshall — All-Pairs Shortest Path
Floyd-Warshall finds the shortest paths between all pairs of vertices in O(V³). It works with negative weights (but not negative cycles) and uses dynamic programming.
public class FloydWarshall {
static final int INF = Integer.MAX_VALUE / 2;
// Floyd-Warshall — O(V³) time, O(V²) space
static void floydWarshall(int[][] dist) {
int V = dist.length;
// For each intermediate vertex k
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
// If path through k is shorter, update
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
static void printMatrix(int[][] dist) {
int V = dist.length;
System.out.println("Shortest distances (all pairs):");
System.out.print(" ");
for (int i = 0; i < V; i++) System.out.printf("%5d", i);
System.out.println();
for (int i = 0; i < V; i++) {
System.out.printf("%3d: ", i);
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF) System.out.printf("%5s", "INF");
else System.out.printf("%5d", dist[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
int V = 4;
int[][] dist = {
{0, 3, INF, 7 },
{8, 0, 2, INF},
{5, INF, 0, 1 },
{2, INF, INF, 0 }
};
floydWarshall(dist);
printMatrix(dist);
}
}
/*
* After Floyd-Warshall:
* 0 1 2 3
* 0: 0 3 5 6
* 1: 5 0 2 3
* 2: 3 6 0 1
* 3: 2 5 7 0
*/Shortest Path Algorithm Comparison
| Algorithm | Type | Time | Negative Weights | Use Case |
|---|---|---|---|---|
| BFS | Single-source | O(V + E) | No (unweighted) | Unweighted graphs |
| Dijkstra | Single-source | O((V+E) log V) | No | GPS, routing |
| Bellman-Ford | Single-source | O(V × E) | Yes | Negative weights, detect neg cycles |
| Floyd-Warshall | All-pairs | O(V³) | Yes (no neg cycles) | Dense graphs, all-pairs |