Shortest Path — Dijkstra and Bellman-Ford Guide

What is the Shortest Path Problem?

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.

Weighted vs Unweighted Graphs

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.

Real-World Motivation

• Maps and GPS: fastest or shortest route between locations.
• Network routing: packets choose low-cost paths through routers.
• Airline planning: choose a cheapest path through flights.
• Game AI: move characters through a map efficiently.
• Operations research: optimize transportation and delivery systems.

How to Choose the Right Algorithm

Algorithm Comparison

1. Dijkstra's Algorithm

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.

Step-by-Step Idea

1. Initialize distance to source as 0 and all other distances as infinity.
2. Insert the source into a min-priority queue.
3. Extract the vertex with the smallest current distance.
4. Relax all outgoing edges from that vertex.
5. Repeat until the queue becomes empty.

Why It Works

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.

When to Prefer Dijkstra

• Road networks with non-negative distances or travel times.
• Network routing problems where all link costs are non-negative.
• Game maps where movement costs are non-negative.

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]);
            }
        }
    }
}

2. Bellman-Ford Algorithm

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.

Step-by-Step Idea

1. Initialize the source distance as 0 and all others as infinity.
2. Relax every edge once.
3. Repeat that full edge scan V-1 times.
4. Run one more pass; if any distance can still be improved, a negative cycle exists.

Key Points

• Works with negative edge weights.
• Detects negative weight cycles.
• Slower than Dijkstra, but more general.

When to Prefer Bellman-Ford

• When negative edges are allowed.
• When negative cycle detection is required.
• When correctness is more important than speed on small or medium graphs.

3. Floyd-Warshall Algorithm

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.

Step-by-Step Idea

1. Start with a distance matrix built from direct edge weights.
2. Pick one vertex k as an allowed intermediate vertex.
3. For every pair (i, j), check whether going through k improves the path.
4. Repeat for all vertices k.

When to Prefer Floyd-Warshall

• When we need shortest distances between every pair of vertices.
• When the graph is relatively small or dense.
• When a simple matrix-based dynamic programming solution is useful.

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();
        }
    }
}

Special Case: Shortest Path in a DAG

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.

Worked Understanding of Relaxation

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.

How to Reconstruct the Actual Path

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.

• Whenever we improve `dist[v]` through `u`, set `parent[v] = u`.
• After the algorithm finishes, start from the destination and move backward through the parent array.
• Reverse that sequence to obtain the path from source to destination.

This is a common interview question because many candidates compute the correct distance but forget how to recover the route itself.

Negative Cycles

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.

• Bellman-Ford: detects a negative cycle if one extra relaxation is still possible after V-1 rounds.
• Floyd-Warshall: detects a negative cycle if some diagonal entry `dist[i][i]` becomes negative.

Important Pitfalls

• Dijkstra fails on negative weights: its greedy choice can become invalid.
• Negative cycle: shortest path is undefined because you can keep decreasing the cost forever.
• Floyd-Warshall is expensive: use it only when all-pairs answers are needed or V is modest.
• BFS applies only to unweighted graphs: or graphs where every edge weight is the same.

Common Questions and Mistakes

• Is the shortest path the one with the fewest edges? Only in unweighted graphs.
• Can Dijkstra handle zero-weight edges? Yes, as long as no edge is negative.
• Does Bellman-Ford always need V-1 full passes? No. It can stop early if no change occurs in a round.
• Is Floyd-Warshall good for very large sparse graphs? Usually no, because O(V^3) is too expensive.
• Do shortest path algorithms always produce a tree? Single-source algorithms usually define a shortest path tree from the source, but the goal is path cost, not spanning all vertices with minimum total edge weight.

Summary Table

Key Takeaways

• BFS is correct for unweighted shortest path problems.
• Dijkstra is the standard choice for non-negative weighted graphs.
• Bellman-Ford handles negative edges and detects negative cycles.
• Floyd-Warshall solves all-pairs shortest path using dynamic programming.
• Path reconstruction requires storing parent or predecessor information.