Shortest Path Algorithms - Tutorials

Shortest path algorithms are fundamental tools in graph theory and are widely used in networking, transportation, AI, and many other domains. This tutorial walks you through the most important algorithms, their theoretical foundations, practical implementations, and guidance on selecting the right method for your problem.

What is a Shortest Path Problem?

Given a weighted graph G = (V, E) where each edge (u, v) has a cost w(u, v), the shortest path problem asks for the minimum‑cost path between a source vertex s and a destination vertex t. Variants include:

Single‑source shortest paths (SSSP)
All‑pairs shortest paths (APSP)
Shortest path with constraints (e.g., negative weights, heuristics)

Key Algorithms Overview

Dijkstra’s Algorithm (non‑negative weights, SSSP)
Bellman‑Ford Algorithm (handles negative weights, detects negative cycles)
Floyd‑Warshall Algorithm (APSP, dense graphs)
A* Search (heuristic‑guided SSSP, often used in path‑finding games)
Johnson’s Algorithm (APSP for sparse graphs with negative edges)

Dijkstra’s Algorithm

Dijkstra’s algorithm efficiently computes the shortest paths from a single source to all other vertices in a graph with non‑negative edge weights. It uses a priority queue (typically a min‑heap) to repeatedly select the vertex with the smallest tentative distance.

💡 Tip: Use a binary heap for O((V + E) log V) time complexity, or a Fibonacci heap for O(V log V + E) if you need the theoretical optimum.

python cpp

import heapq

def dijkstra(graph, start):
    # graph: {node: [(neighbor, weight), ...]}
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        cur_dist, u = heapq.heappop(pq)
        if cur_dist > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

#include <bits/stdc++.h>
using namespace std;

vector<long long> dijkstra(const vector<vector<pair<int,int>>>& adj, int src) {
    const long long INF = 1e18;
    int n = adj.size();
    vector<long long> dist(n, INF);
    dist[src] = 0;
    using P = pair<long long,int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

⚠ Warning: Dijkstra’s algorithm does **not** work correctly with negative‑weight edges. Use Bellman‑Ford instead if negative edges may appear.

Bellman‑Ford Algorithm

Bellman‑Ford relaxes all edges |V|‑1 times, guaranteeing correct distances even when negative weights exist. It also detects negative‑weight cycles reachable from the source.

📝 Note: The algorithm runs in O(V·E) time, which is slower than Dijkstra’s but essential when negative weights are present.

java

public class BellmanFord {
    static final int INF = Integer.MAX_VALUE;
    static int[] bellmanFord(int[][] edges, int V, int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        // Edge list: {u, v, w}
        for (int i = 1; i <= V - 1; i++) {
            for (int[] e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] != INF && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
        // Check for negative cycles
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                throw new IllegalArgumentException("Graph contains a negative-weight cycle");
            }
        }
        return dist;
    }
}

Floyd‑Warshall Algorithm

Floyd‑Warshall computes shortest paths between **all** pairs of vertices in a dense graph. It iteratively improves the distance matrix using the recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

Algorithm	Time Complexity	Space Complexity	Suitable Graphs
Dijkstra (binary heap)	O((V+E) log V)	O(V)	Sparse, non‑negative weights
Bellman‑Ford	O(V·E)	O(V)	Graphs with negative weights
Floyd‑Warshall	O(V³)	O(V²)	Dense graphs, APSP
A* Search	O(b^d) (depends on heuristic)	O(V)	Path‑finding with good heuristic

python

def floyd_warshall(weight):
    # weight: adjacency matrix, INF for no edge
    n = len(weight)
    dist = [row[:] for row in weight]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

A* Search Algorithm

A* combines Dijkstra’s uniform‑cost search with a heuristic h(v) that estimates the cost from v to the goal. When h is admissible (never overestimates), A* is guaranteed to find an optimal path.

💡 Tip: For grid‑based maps, the Manhattan distance (|dx| + |dy|) or Euclidean distance (√(dx²+dy²)) are common heuristics.

python

import heapq

def a_star(graph, start, goal, heuristic):
    open_set = [(0, start)]
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0
    f_score = {node: float('inf') for node in graph}
    f_score[start] = heuristic(start, goal)
    while open_set:
        _, current = heapq.heappop(open_set)
        if current == goal:
            return g_score[goal]
        for neighbor, weight in graph[current]:
            tentative_g = g_score[current] + weight
            if tentative_g < g_score[neighbor]:
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score[neighbor], neighbor))
    raise ValueError('No path found')

Choosing the Right Algorithm

Identify edge weight characteristics (negative? non‑negative?).
Determine if you need single‑source or all‑pairs results.
Consider graph density: sparse vs. dense.
Check if a heuristic is available (for A*).
Pick the algorithm that matches the above criteria.

📘 Summary: Dijkstra excels on non‑negative, sparse graphs; Bellman‑Ford handles negative edges and cycle detection; Floyd‑Warshall is ideal for dense graphs when APSP is required; A* offers speedups when a good heuristic exists. Understanding these trade‑offs lets you apply the most efficient solution to real‑world routing problems.

Q: Can Dijkstra be used on graphs with negative edges?
A: No. Dijkstra assumes all edge weights are non‑negative. Use Bellman‑Ford or Johnson’s algorithm for graphs that contain negative edges.

Q: What is the difference between Bellman‑Ford and Johnson’s algorithm?
A: Bellman‑Ford solves SSSP and detects negative cycles in O(V·E). Johnson’s algorithm reweights the graph using Bellman‑Ford and then runs Dijkstra from each vertex, achieving O(V·E log V) for APSP on sparse graphs with negative edges.

Q: When should I prefer A* over Dijkstra?
A: Use A* when you have a reliable admissible heuristic that estimates the remaining distance to the goal. This often reduces the number of explored nodes dramatically, especially in grid or geographic maps.

Q. Which algorithm guarantees detection of a negative‑weight cycle reachable from the source?

Dijkstra
Bellman‑Ford
Floyd‑Warshall
A*

Answer: Bellman‑Ford
Bellman‑Ford performs an extra relaxation pass to check for further distance reductions, which indicates a negative‑weight cycle.

Q. What is the time complexity of Floyd‑Warshall?

O(V log V)
O(V·E)
O(V³)
O(E²)

Answer: O(V³)
The algorithm uses three nested loops over all vertices, resulting in cubic time.

References

🎥 Video

Tags: Shortest Path Algorithms Graph Theory Dijkstra Bellman-Ford Floyd-Warshall A* Programming

#ad