Bellman Ford Algorithm

Author: @wingkwong

Overview

Bellman Ford Algorithm computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. Similar to Dijkstra's algorithm, it proceeds by relaxation. However, Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not been processed, which all of its outgoing edges will be processed. On the other hand, Bellman Ford Algorithm relaxes all the edges and does the relaxation only $|V| - 1$ times where $|V|$ is the number of vertices in the graph. This is because given a graph with no negative weight cycles with $V$ vertices, the shortest path between any two vertices has at most $|V| - 1$ edges.

Implementation

C++

Written by @wingkwong

template<typename T_a3, typename T_vector>
void bellman_ford(T_a3 &g, T_vector &dist, int src, int mx_edges) {
    dist[src] = 0;
    for (int i = 0; i <= mx_edges; i++) {
        T_vector ndist = dist;
        for (auto x : g) {
            auto [from, to, cost] = x;
            ndist[to] = min(ndist[to], dist[from] + cost);
        }
        dist = ndist;
    }
}

Python

Written by @Odion-Sonny

def bellman_ford(g, dist, src, mx_edges):
    dist[src] = 0
    for i in range(mx_edges + 1):
        ndist = dist[:]
        for x in g:
            _from, to, cost = x
            ndist[to] = min(ndist[to], dist[_from] + cost)
        dist = ndist
    return dist