Bellman-Ford — SSSP with Negative Edges and Cycle Detection

for V-1 times:
    for each edge (u, v, w):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

for each edge (u, v, w):
    if dist[u] + w < dist[v]:
        → negative cycle detected

def bellman_ford(n, edges, src):
    dist = [float('inf')]*n
    dist[src] = 0
    for _ in range(n-1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u]+w < dist[v]:
                dist[v] = dist[u]+w
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u]+w < dist[v]:
            return None
    return dist

function bellmanFord(n, edges, src) {
    const dist=new Array(n).fill(Infinity); dist[src]=0;
    for(let i=0;i<n-1;i++)
        for(const[u,v,w]of edges)
            if(dist[u]!==Infinity&&dist[u]+w<dist[v])dist[v]=dist[u]+w;
    for(const[u,v,w]of edges)
        if(dist[u]!==Infinity&&dist[u]+w<dist[v])return null;
    return dist;
}

public int[] bellmanFord(int n, int[][] edges, int src) {
    int[] dist=new int[n]; java.util.Arrays.fill(dist,Integer.MAX_VALUE/2); dist[src]=0;
    for(int i=0;i<n-1;i++)
        for(int[]e:edges) if(dist[e[0]]<Integer.MAX_VALUE/2&&dist[e[0]]+e[2]<dist[e[1]])dist[e[1]]=dist[e[0]]+e[2];
    for(int[]e:edges) if(dist[e[0]]<Integer.MAX_VALUE/2&&dist[e[0]]+e[2]<dist[e[1]])return null;
    return dist;
}

#include <vector>
#include <climits>
using namespace std;
vector<int> bellmanFord(int n,vector<array<int,3>>&edges,int src){
    vector<int> dist(n,INT_MAX/2); dist[src]=0;
    for(int i=0;i<n-1;i++)for(auto&e:edges)if(dist[e[0]]<INT_MAX/2&&dist[e[0]]+e[2]<dist[e[1]])dist[e[1]]=dist[e[0]]+e[2];
    for(auto&e:edges)if(dist[e[0]]<INT_MAX/2&&dist[e[0]]+e[2]<dist[e[1]])return{};
    return dist;
}

void bellman_ford(int* dist,int n,int edges[][3],int m,int src){
    for(int i=0;i<n;i++)dist[i]=1e9; dist[src]=0;
    for(int i=0;i<n-1;i++)for(int j=0;j<m;j++)
        if(dist[edges[j][0]]<1e9&&dist[edges[j][0]]+edges[j][2]<dist[edges[j][1]])dist[edges[j][1]]=dist[edges[j][0]]+edges[j][2];
}