Shortest Paths

Two problems

Given a weighted graph G = (V, E) with edge weights w(u, v):

• Single-source shortest path (SSSP): the minimum-cost path from one source vertex s to all other vertices.
• All-pairs shortest path (APSP): the minimum-cost path between every pair of vertices.
• Negative-weight edges are allowed in some algorithms, but negative cycles make shortest paths undefined.

Idea and steps

Repeatedly pick the unvisited vertex with the smallest current distance, then relax all its outgoing edges — the straightforward O(V²) version.

1. Initialise dist[v] = INF for all vertices, mark all unvisited; set dist[s] = 0.
2. Repeat n times: choose the unvisited vertex v with the smallest dist[v] — if it is unreachable (INF), stop; mark v visited; for every edge (v, to, w), if dist[v] + w < dist[to], update dist[to] and record p[to] = v.
3. After processing, dist holds the shortest distances from s.

Complexity and use cases

• With a simple linear scan for the next vertex: O(V² + E) — often shown for clarity or for dense graphs.
• Routing with non-negative costs: road networks, network latency.
• A subroutine in A* search (with heuristics).

The program

Selects the next vertex with a linear scan instead of a priority queue. Vertices are 0 … n − 1, the graph is directed; input is n m s, then u v w per edge.

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

const int INF = 1000000000;

int main() {
    int n, m, s; // vertices are 0..n-1
    cin >> n >> m >> s;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        // add g[v].push_back({u, w}); for an undirected graph
    }

    vector<int> d(n, INF), p(n, -1);
    vector<char> used(n, false);
    d[s] = 0;

    for (int i = 0; i < n; ++i) {
        int v = -1;
        for (int j = 0; j < n; ++j)
            if (!used[j] && (v == -1 || d[j] < d[v]))
                v = j;
        if (v == -1 || d[v] == INF)
            break;
        used[v] = true;

        for (auto [to, len] : g[v]) {
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }

    // d now holds shortest paths from s; p stores the tree for reconstruction
    for (int v = 0; v < n; v++)              // added: print the distances
        cout << (d[v] == INF ? -1 : d[v]) << " ";
    cout << "\n";
}

5 6 0
0 1 2
0 2 5
1 3 2
1 2 1
2 3 3
3 4 1

0 2 3 4 5

Walkthrough on a small graph

A 5-vertex directed graph with non-negative weights; Dijkstra from source 0.

   0 --2--> 1 --2--> 3 --1--> 4
   |        |        ^
   5        1        |
   v        |        |
   2 <------+        |
   |                 |
   +--------3--------+

Edges: 0→1 (2), 0→2 (5), 1→3 (2), 1→2 (1), 2→3 (3), 3→4 (1).

Initialisation: dist = [0, INF, INF, INF, INF], nothing visited.

Step 2 is the interesting one: going through 1 makes vertex 2 cheaper — 2 + 1 = 3 instead of the direct 5. Final distances [0, 2, 3, 4, 5].

Another version · undirected, with the path

The same O(V²) loop on global arrays, for an undirected graph with vertices from 1. After the distances it reads the target f and prints the path, walking the parents back from f to s:

int f;
cin >> f;
f--;
int old_f = f;
vector<int> result;
while (p[f] != f) {
    result.pb(f);
    f = p[f];
}
result.pb(s);
for (int i = result.size() - 1; i >= 0; i--) 
    cout << result[i] + 1 << " ";
cout << endl;
cout << d[old_f];

The path comes out backwards, so it is printed from the end. The source is its own parent (p[s] = s), which is what stops the walk.

#include <iostream>
#include <vector>
#define pb push_back
#define mp make_pair
#define f first
#define s second 

using namespace std;
vector<pair<int, int> > g[100];
int INF = 100000;
int d[100];
int p[100];
int u[100];
int n, m, x, y, w, s;

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> w;
        x--;
        y--;
        g[x].pb(mp(y, w));
        g[y].pb(mp(x, w));
    }
    for (int i = 0; i < n; i++)
        d[i] = INF;
    cin >> s; 
    cout << s << endl;
    s--;
    d[s] = 0;
    p[s] = s;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++)
            if (u[j] == 0)
                if (v == -1 || d[v] > d[j])
                    v = j;
        u[v] = true; // S ------> V (d[v]) ---W-- to (d[to])
                     // S ----------------------> to (d[to])
        for (int j = 0; j < g[v].size(); j++) {
            int to = g[v][j].f;
            int w = g[v][j].s;
            if (u[to] == 0 && d[to] > d[v] + w) {
                d[to] = d[v] + w;
                p[to] = v;
            }
        }
    }
    // for (int i = 0; i < n; i++) {
    //     cout << d[i] << " ";
    // }
    // cout << endl;
    // for (int i = 0; i < n; i++) {
    //     cout << p[i] + 1 << " ";
    // }
    int f;
    cin >> f;
    f--;
    int old_f = f;
    vector<int> result;
    while (p[f] != f) {
        result.pb(f);
        f = p[f];
    }
    result.pb(s);
    for (int i = result.size() - 1; i >= 0; i--) 
        cout << result[i] + 1 << " ";
    cout << endl;
    cout << d[old_f];
    return 0;
}

6 10
1 3 5
1 4 1
2 3 1
2 4 1
2 5 3
2 6 5
3 5 1
3 4 3
4 5 6
5 6 2
1 6

1
1 4 2 3 5 6
6

It prints the source, the path 1 → 4 → 2 → 3 → 5 → 6, and its length 6.

Idea and steps

Relax every edge V − 1 times; if an edge can still be relaxed once more, a negative cycle exists.

1. Initialise dist[s] = 0, all others to INF.
2. Repeat V − 1 times: for each edge (u, v, w), if dist[u] + w < dist[v], update dist[v].
3. To detect negative cycles reachable from s, run one more pass; any improvement means a negative cycle.

Complexity and use cases

• Graphs with negative edges: currency arbitrage detection, balancing flows.
• A preprocessing step before reweighting edges in Johnson's algorithm.

The program — edge list

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

struct Edge { int u, v, w; };

int main() {
    const long long INF = 4e18;
    int n, m, s; // vertices 0..n-1
    cin >> n >> m >> s;
    vector<Edge> edges(m);
    for (auto &e : edges) cin >> e.u >> e.v >> e.w;

    vector<long long> dist(n, INF);
    dist[s] = 0;

    for (int i = 0; i < n - 1; i++) {
        bool changed = false;
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }
        if (!changed) break; // early exit if no updates
    }

    bool has_neg_cycle = false;
    for (auto [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            has_neg_cycle = true;
            break;
        }
    }

    // dist holds shortest paths unless a reachable negative cycle exists
    if (has_neg_cycle) cout << "negative cycle\n";   // added: print the result
    else {
        for (int v = 0; v < n; v++)
            cout << (dist[v] == INF ? -1 : dist[v]) << " ";
        cout << "\n";
    }
}

4 4 0
0 1 4
0 2 5
2 3 -2
3 1 1

0 4 5 3

Walkthrough with a negative edge

A 4-vertex directed graph with a negative edge but no negative cycle; source 0.

   0 --4--> 1
   |        ^
   5        1
   v        |
   2 -(-2)-> 3

Edges, in the order they are relaxed: 0→1 (4), 0→2 (5), 2→3 (-2), 3→1 (1).

Initialisation: dist = [0, INF, INF, INF]. Up to V − 1 = 3 passes, every edge each pass:

Pass 2 changes nothing, so the loop stops early. The route 0 → 2 → 3 → 1 costs 5 − 2 + 1 = 4 — exactly as much as the direct edge, so dist[1] stays 4. The extra cycle-detection pass finds no improvement either: no reachable negative cycle. Final [0, 4, 5, 3].

Idea and steps

Dynamic programming over intermediate vertices: after processing vertices 0 … k, dist[i][j] stores the shortest path from i to j using only those as intermediates.

1. Initialise dist[i][j] with the edge weights (INF if there is no edge) and dist[i][i] = 0.
2. For each intermediate vertex k from 0 to V − 1, for each pair (i, j): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
3. After the loops dist holds all-pairs distances. A negative cycle shows up as some dist[i][i] < 0.

Complexity and use cases

• Dense graphs where V³ is acceptable.
• Transitive closure — replace the sums with boolean OR / AND.
• Routing tables, or minimum distances inside DP over subsets (e.g. TSP).

The program — adjacency matrix

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

int main() {
    const long long INF = 4e18;
    int n; // vertices 0..n-1
    cin >> n;
    vector<vector<long long>> dist(n, vector<long long>(n, INF));

    for (int i = 0; i < n; i++) dist[i][i] = 0;
    int m; cin >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], 1LL * w); // handle multi-edges
    }

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] < INF && dist[k][j] < INF &&   // fixed: never extend an unreachable path
                    dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];

    // dist[i][j] now holds APSP results
    for (int i = 0; i < n; i++) {             // added: print the matrix
        for (int j = 0; j < n; j++)
            if (dist[i][j] == INF) cout << "INF ";
            else cout << dist[i][j] << " ";
        cout << "\n";
    }
}

3
3
0 1 3
0 2 8
1 2 1

0 3 4
INF 0 1
INF INF 0

The check dist[i][k] < INF && dist[k][j] < INF matters once weights can be negative: without it an unreachable pair would get INF plus a negative number — a value just below INF that no longer reads as "no path".

Walkthrough — the matrix, k by k

Three vertices and the directed edges 0→1 (3), 0→2 (8), 1→2 (1); INF means no direct edge.

   0 --3--> 1
    \       |
     8      1
      \     v
       +--> 2

Initial dist

k = 0 — paths through vertex 0: no improvements.

k = 1 — paths through vertex 1: dist[0][2]: 8 → 3 + 1 = 4 (path 0 → 1 → 2). Matrix becomes:

k = 2 — paths through vertex 2: no improvements.

Each intermediate vertex can only tighten paths between pairs. If some dist[i][i] became negative, that would mean a negative cycle.

Which one when

• Dijkstra: fast for non-negative weights and large sparse graphs.
• Bellman-Ford: works with negative weights and detects negative cycles, but is slower.
• Floyd–Warshall: all-pairs results for dense graphs; easy to adapt for path reconstruction or transitive closure.

Problem to topic