Shortest Path

Algorithms for finding shortest paths: Dijkstra, Bellman-Ford, Floyd-Warshall

Shortest Path Algorithms

Finding shortest paths is a fundamental problem commonly found in competitions. There are several algorithms suitable for different situations.

Overview

Algorithm	Graph Type	Complexity	Use Case
BFS	Unweighted	$O(V+E)$	Edge weight = 1
Dijkstra	Non-negative weights	$O((V+E) \log V)$	Single source
Bellman-Ford	Any weights	$O(VE)$	Negative weights
Floyd-Warshall	Any weights	$O(V^3)$	All pairs

Dijkstra’s Algorithm

Finds shortest path from single source to all vertices in a graph with non-negative edge weights.

Algorithm

Set distance of source = 0, rest = $\infty$
Use priority queue to store (distance, vertex)
Extract vertex with minimum distance
Update distances of neighbors (relaxation)
Repeat until priority queue is empty

Implementation

const int INF = 1e9;

vector<int> dijkstra(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue; // Skip outdated entries
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

Dijkstra with Path Reconstruction

pair<vector<int>, vector<int>> dijkstraWithPath(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INF);
    vector<int> parent(n, -1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    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;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
    
    return {dist, parent};
}

vector<int> getPath(int end, vector<int>& parent) {
    vector<int> path;
    for (int v = end; v != -1; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

Complexity

Time: $O((V + E) \log V)$ with priority queue
Space: $O(V)$

Bellman-Ford Algorithm

Finds shortest path from single source and supports negative edge weights with negative cycle detection.

Algorithm

Set distance of source = 0, rest = $\infty$
Relax all edges $V-1$ times
Check for negative cycle (if can still relax, there’s a cycle)

Implementation

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

vector<int> bellmanFord(int start, int n, vector<Edge>& edges) {
    vector<int> dist(n + 1, INF);
    dist[start] = 0;
    
    // Relax V-1 times
    for (int i = 0; i < n - 1; i++) {
        for (auto& e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
            }
        }
    }
    
    // Check for negative cycle
    for (auto& e : edges) {
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
            // Negative cycle detected
            return {}; // or handle according to problem
        }
    }
    
    return dist;
}

Bellman-Ford with Negative Cycle Detection

bool hasNegativeCycle(int n, vector<Edge>& edges) {
    vector<int> dist(n + 1, 0); // Start from 0 for all vertices
    
    for (int i = 0; i < n; i++) {
        bool updated = false;
        for (auto& e : edges) {
            if (dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                updated = true;
            }
        }
        if (!updated) break;
    }
    
    // If updated in round n, there's a negative cycle
    for (auto& e : edges) {
        if (dist[e.u] + e.w < dist[e.v]) {
            return true;
        }
    }
    return false;
}

Complexity

Time: $O(VE)$
Space: $O(V)$

Floyd-Warshall Algorithm

Finds shortest path between all pairs of vertices.

Algorithm (Dynamic Programming)

$dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])$

Where $k$ is the intermediate vertex.

Implementation

void floydWarshall(vector<vector<int>>& dist) {
    int n = dist.size();
    
    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) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

Setup and Usage

int main() {
    int n, m;
    cin >> n >> m;
    
    // Initialize
    vector<vector<int>> dist(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    
    // Read edges
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w); // if undirected
    }
    
    floydWarshall(dist);
    
    // dist[i][j] = shortest path from i to j
}

Detecting Negative Cycle

bool hasNegativeCycleFloyd(vector<vector<int>>& dist) {
    floydWarshall(dist);
    int n = dist.size();
    
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) return true;
    }
    return false;
}

Path Reconstruction

vector<vector<int>> next_node;

void floydWarshallWithPath(vector<vector<int>>& dist) {
    int n = dist.size();
    next_node.assign(n, vector<int>(n, -1));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] != INF && i != j) {
                next_node[i][j] = j;
            }
        }
    }
    
    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) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next_node[i][j] = next_node[i][k];
                    }
                }
            }
        }
    }
}

vector<int> getPathFloyd(int u, int v) {
    if (next_node[u][v] == -1) return {}; // No path
    
    vector<int> path = {u};
    while (u != v) {
        u = next_node[u][v];
        path.push_back(u);
    }
    return path;
}

Complexity

Time: $O(V^3)$
Space: $O(V^2)$

SPFA (Shortest Path Faster Algorithm)

Faster version of Bellman-Ford (average case).

vector<int> spfa(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INF);
    vector<bool> inQueue(n, false);
    queue<int> q;
    
    dist[start] = 0;
    q.push(start);
    inQueue[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
    
    return dist;
}

Complexity: $O(VE)$ worst case, but often faster in practice.

Which Algorithm to Use?

What's the graph like?
│
├── Edge weights = 1 (or none)
│   └── BFS O(V+E)
│
├── Non-negative weights
│   ├── Single source → Dijkstra O((V+E)log V)
│   └── All pairs → Floyd-Warshall O(V³) or Dijkstra V times
│
└── Has negative weights
    ├── Detect negative cycle → Bellman-Ford O(VE)
    └── All pairs → Floyd-Warshall O(V³)

Example Problems

Problem: Find Shortest Path Between Two Nodes

int main() {
    int n, m, start, end;
    cin >> n >> m >> start >> end;
    
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // undirected
    }
    
    auto dist = dijkstra(start, adj);
    
    if (dist[end] == INF) {
        cout << -1 << endl; // No path
    } else {
        cout << dist[end] << endl;
    }
}

Summary

Situation	Algorithm
Unweighted graph	BFS
Non-negative weights, single source	Dijkstra
Negative weights, single source	Bellman-Ford / SPFA
All pairs, small V	Floyd-Warshall
Detect negative cycle	Bellman-Ford

💡 Tip: If graph has edge weights of 0 or 1, use 0-1 BFS which is faster than Dijkstra.