Shortest path problems in graph theory often rely on the concept of relaxation. Relaxation occurs when a path from node u to v can be shoretned by routing through an intermediate node k, i.e., if dist[u][v] > dist[u][k] + dist[k][v], we update dist[u][v] accordingly.

Floyd-Warshall Algorithm (All-Pairs Shortest Paths)

To compute shortest paths between all pair of vertices, the Floyd-Warshall algorithm uses dynamic programming. Define dp[k][i][j] as the shortest distance from i to j using only vertices numbered from 1 to k as intermediates. The recurrence is:

dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

Since each state depends only on the previous layer (k-1), we can optimize space by using a 2D array and iterating k in the outermost loop:

for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

This yields the all-pairs shortest paths in O(n³) time with O(n²) space.

SPFA (Single-Source Shortest Paths)

For single-source shortest paths, especially in graphs with negative weights (but no negative cycles), the Shortest Path Faster Algorithm (SPFA)—a queue-optimized version of Bellman-Ford—is effective.

Maintain an array dist[] where dist[v] stores the shortest distance from the source s to v. Initialize dist[s] = 0 and others to infinity. Use a queue to process nodes whose outgoing edges might relax neighboring distances.

When relaxing an edge u → v with weight w, if dist[v] > dist[u] + w, update dist[v] and enqueue v—but only if it’s not already in the queue (tracked via a inQueue[] boolean array).

void spfa(int source) {
    queue<int> q;
    vector<bool> inQueue(n, false);
    vector<int> dist(n, INT_MAX);
    
    dist[source] = 0;
    q.push(source);
    inQueue[source] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;

        for (auto &edge : adj[u]) {
            int v = edge.to;
            int weight = edge.weight;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
}

Although SPFA has a worst-case time complexity of O(VE), it often performs efficiently in practice on sparse graphs or those without adversarial edge structures.