The shortest path problem asks for a path between vertices whose total cost is minimum. The cost may represent distance, time, price, latency, or any other weight assigned to edges. It is one of the most important families of graph problems because many real systems can be modeled as weighted networks.
| Problem Type | Meaning | Typical Algorithms |
|---|---|---|
| Single-source shortest path | Shortest paths from one source to all vertices | BFS, Dijkstra, Bellman-Ford |
| Single-pair shortest path | Shortest path between one source and one target | BFS, Dijkstra, A* |
| All-pairs shortest path | Shortest paths for every ordered pair of vertices | Floyd-Warshall |
| Graph Type | Meaning | Best Basic Approach |
|---|---|---|
| Unweighted graph | Every edge has the same cost, usually treated as 1 | BFS |
| Weighted graph | Edges may have different costs | Dijkstra, Bellman-Ford, Floyd-Warshall |
This distinction is very important. BFS is correct for shortest path only when all edges have equal weight. Once edge costs differ, we need algorithms that compare total path cost, not just the number of edges.
| Situation | Best Choice | Reason |
|---|---|---|
| Unweighted graph | BFS | Each edge has equal cost, so level order gives shortest path |
| Weighted graph with non-negative edges | Dijkstra | Fast and optimal under non-negative weights |
| Negative edge weights may exist | Bellman-Ford | Can handle negative edges and detect negative cycles |
| Need distances between every pair | Floyd-Warshall | Dynamic programming solution for APSP |
| Algorithm | Works On | Time Complexity | Negative Weights | Main Idea |
|---|---|---|---|---|
| BFS | Unweighted graphs | O(V + E) | Not applicable | Explore level by level |
| Dijkstra | Weighted graphs | O((V + E) log V) | No | Greedily finalize closest vertex |
| Bellman-Ford | Weighted graphs | O(VE) | Yes | Relax all edges repeatedly |
| Floyd-Warshall | All-pairs problem | O(V^3) | Yes, if no negative cycle | Dynamic programming over intermediate vertices |
Dijkstra's algorithm solves the single-source shortest path problem when all edge weights are non-negative. It keeps track of the currently best known distance to every vertex and repeatedly selects the unprocessed vertex with the smallest distance.
Because all weights are non-negative, once the minimum-distance vertex is removed from the priority queue, there cannot be a cheaper path to it later. That is the greedy property that makes Dijkstra correct.
import java.util.*;
public class Dijkstra {
static int V;
static List<int[]>[] adj; // {neighbor, 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 graph
}
static int[] dijkstra(int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq =
new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, src});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int d = current[0];
int u = current[1];
if (d > dist[u]) continue; // outdated entry
for (int[] edge : adj[u]) {
int v = edge[0];
int 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);
for (int i = 0; i < V; i++) {
System.out.println("Distance from 0 to " + i + " = " + dist[i]);
}
}
}import java.util.Arrays;
public class BellmanFord {
static int V;
static int[][] edges; // {u, v, weight}
static int[] bellmanFord(int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 1; i < V; i++) {
boolean changed = false;
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;
changed = true;
}
}
if (!changed) break;
}
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;
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) {
for (int i = 0; i < V; i++) {
System.out.println("Distance from 0 to " + i + " = " + dist[i]);
}
}
}
}Bellman-Ford is used when edge weights may be negative. Instead of greedily finalizing vertices, it repeatedly relaxes every edge. After at most V-1 rounds, all shortest paths without cycles have been considered.
Floyd-Warshall solves the all-pairs shortest path problem. It uses dynamic programming and gradually allows more intermediate vertices in a path. After processing vertex k, the algorithm knows the shortest paths that are allowed to use only vertices 0 through k as intermediates.
public class FloydWarshall {
static final int INF = 1_000_000_000;
static void floydWarshall(int[][] dist) {
int V = dist.length;
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
public static void main(String[] args) {
int[][] dist = {
{0, 3, INF, 7},
{8, 0, 2, INF},
{5, INF, 0, 1},
{2, INF, INF, 0}
};
floydWarshall(dist);
for (int i = 0; i < dist.length; i++) {
for (int j = 0; j < dist.length; j++) {
System.out.print(dist[i][j] + " ");
}
System.out.println();
}
}
}If the graph is a Directed Acyclic Graph (DAG), shortest paths can be found faster using topological order. After computing a topological ordering, relax edges in that order. This works even if some edge weights are negative, because DAGs do not contain cycles.
| Graph Type | Technique | Time Complexity |
|---|---|---|
| DAG | Topological order + edge relaxation | O(V + E) |
Relaxation is the basic operation behind shortest path algorithms. For an edge u -> v with weight w, if we already know a path to u, we test whether going through u gives a better path to v:
if dist[u] + w < dist[v], then update dist[v]
Dijkstra performs relaxation in a greedy order. Bellman-Ford performs relaxation across all edges repeatedly. Floyd-Warshall performs relaxation using every vertex as a possible intermediate point.
Many shortest path algorithms first compute only the minimum distance values. If we also want the actual path, we maintain a parent or predecessor array.
This is a common interview question because many candidates compute the correct distance but forget how to recover the route itself.
A negative cycle is a cycle whose total edge weight is negative. If such a cycle is reachable from the source, the shortest path is not well-defined because we can keep going around the cycle and make the total path cost smaller and smaller.
| If the graph has... | Use... |
|---|---|
| No weights | BFS |
| Non-negative weights | Dijkstra |
| Negative weights | Bellman-Ford |
| Need all-pairs distances | Floyd-Warshall |
Explore 500+ free tutorials across 20+ languages and frameworks.