Shortest Path Dijkstra Bellman Ford

Shortest in DAA is best learned by connecting the rule to an interview-style problem. Start with the smallest algorithm step, observe the output, and then add one realistic constraint so the concept becomes practical.

The key habit for this lesson is to watch input graph, array, or recurrence as it changes. That makes the topic easier to debug, easier to explain in interviews, and easier to use in real code without memorizing isolated syntax.

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.

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

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.

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

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

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 Comparison

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

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.

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.

Initialize distance to source as 0 and all other distances as infinity.
Insert the source into a min-priority queue.
Extract the vertex with the smallest current distance.
Relax all outgoing edges from that vertex.
Repeat until the queue becomes empty.
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.

Dijkstra and Bellman-Ford

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

1. Dijkstra's Algorithm

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.

Initialize the source distance as 0 and all others as infinity.
Relax every edge once.
Repeat that full edge scan V-1 times.
Run one more pass; if any distance can still be improved, a negative cycle exists.
Works with negative edge weights.
Detects negative weight cycles.
Slower than Dijkstra, but more general.
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.

Start with a distance matrix built from direct edge weights.
Pick one vertex k as an allowed intermediate vertex.
For every pair (i, j), check whether going through k improves the path.
Repeat for all vertices k.
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.

Floyd-Warshall All-Pairs Shortest Path

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.

Graph Type	Technique	Time Complexity
DAG	Topological order + edge relaxation	O(V + E)

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.

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

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.

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

If the graph has...	Use...
No weights	BFS
Non-negative weights	Dijkstra
Negative weights	Bellman-Ford
Need all-pairs distances	Floyd-Warshall

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.

Applied guide for Shortest

Use Shortest when the program needs a clear answer to a specific problem, not because the keyword looks familiar. In a real DAA task, first name the input, then name the transformation, then name the output. This small discipline shows whether the topic is being used correctly or only copied from an example.

A reliable practice flow is: create the smallest working algorithm step, add one normal case, add one edge case such as loading, error, and empty states, and then confirm the result with trace table and complexity count. If the result surprises you, reduce the code until the behavior is visible again.

The most common trap here is testing implementation details instead of behavior. Avoid it by writing one sentence before the code that explains why Shortest is the right choice. After the code runs, verify the lesson by doing this: make the failing assertion describe user-visible output.

Identify the exact problem solved by Shortest.
Trace input graph, array, or recurrence before and after the main operation.
Keep one intentionally broken version and explain the fix.
Connect the example to an interview-style problem so the idea feels concrete.

Key Takeaways

I can explain where Shortest fits inside an interview-style problem.
I can point to the exact input graph, array, or recurrence affected by this topic.
I tested a normal case and an edge case involving loading, error, and empty states.
I verified the result with trace table and complexity count instead of assuming it worked.
I can describe the main mistake: testing implementation details instead of behavior.

Common Mistakes to Avoid

WRONG Testing implementation details instead of behavior.

RIGHT Write the expected behavior first, then make the example prove it.

A one-line expectation turns the code from copied syntax into a testable idea.

WRONG Practicing only the perfect input.

RIGHT Also test loading, error, and empty states before considering the lesson complete.

The edge case is where most interview follow-up questions begin.

WRONG Looking only at the final output.

RIGHT Trace input graph, array, or recurrence through each important step.

Tracing makes debugging faster because you can see the first incorrect state.

Practice Tasks

Build one small algorithm step that demonstrates Shortest in an interview-style problem.
Change the example to include loading, error, and empty states and record the difference.
Break the example by deliberately testing implementation details instead of behavior, then write the corrected version.
Explain the finished example in five bullet points: input, operation, output, failure case, and verification.

Frequently Asked Questions

When should I use Shortest?

Use it when the problem matches the behavior shown in the example and when the result can be verified through trace table and complexity count.

How do I avoid mistakes in Shortest?

Start with a tiny case, then test loading, error, and empty states. The main warning sign is testing implementation details instead of behavior.

How can I revise Shortest quickly?

Trace input graph, array, or recurrence, predict the result, run the example, and compare your prediction with the actual output.

Previous Next

Shortest Path Dijkstra Bellman Ford