Theory

• Bellman–Ford algorithm

Implementation

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

struct Edge{
    int u, v, w;
};
class BellmanFord {
private:
    int const INF = numeric_limits<int>::max();
public:
    // NOTE: This implementation assumes there are no negative cycles in the graph.
    int shortestPath(vector<Edge>& edges, int n, int src, int dst) {
        vector<int> dist(n + 1, INF);
        dist[src] = 0;
        for (int i = 1; i <= n - 1; i++) {
            for (auto edge : edges) {
                int u = edge.u;
                int v = edge.v;
                int w = edge.w;
                if (dist[u] == INF) { continue; }
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        if (dist[dst] == INF) { return -1; }
        return dist[dst];
    }
};

Practice problems

• https://leetcode.com/problems/network-delay-time/
• https://leetcode.com/problems/cheapest-flights-within-k-stops/