Thuật toán Bellman-Ford

1def bellman_ford(vertices, edges, start):2    dist = {v: float("inf") for v in vertices}3    dist[start] = 04    # Relax every edge V-1 times5    for _ in range(len(vertices) - 1):6        for u, v, w in edges:7            if dist[u] + w < dist[v]:8                dist[v] = dist[u] + w9    # One more pass: any improvement means a negative cycle10    for u, v, w in edges:11        if dist[u] + w < dist[v]:12            raise ValueError("Graph contains a negative-weight cycle")13    return dist14
15
16vertices = ["A", "B", "C", "D", "E"]17edges = [18    ("A", "B", 6), ("A", "C", 7), ("B", "D", 5), ("B", "E", -4),19    ("C", "D", -3), ("D", "B", -2), ("E", "D", 7),20]21
22for node, d in bellman_ford(vertices, edges, "A").items():23    print(f"A -> {node}: {d}")

1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3    ["A", "B", 6], ["A", "C", 7], ["B", "D", 5], ["B", "E", -4],4    ["C", "D", -3], ["D", "B", -2], ["E", "A", 2],5];6
7function bellmanFord(source) {8    const dist = Object.fromEntries(nodes.map((n) => [n, Infinity]));9    dist[source] = 0;10    // Relax every edge V-1 times11    for (let i = 0; i < nodes.length - 1; i++) {12        for (const [u, v, w] of edges) {13            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;14        }15    }16    // One more pass: any improvement means a negative cycle17    for (const [u, v, w] of edges) {18        if (dist[u] + w < dist[v]) throw new Error("Negative cycle detected");19    }20    return dist;21}22
23console.log("Shortest distances from A:", bellmanFord("A"));

1import java.util.Arrays;2
3public class Main {4    public static void main(String[] args) {5        int n = 5;6        // Directed edges {from, to, weight}; negative weights allowed7        int[][] edges = {8            {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {1, 2, 8},9            {2, 4, 9}, {3, 1, -2}, {4, 3, 7}, {2, 3, -3}10        };11        int[] dist = new int[n];12        Arrays.fill(dist, Integer.MAX_VALUE);13        dist[0] = 0;14
15        // Relax every edge V-1 times16        for (int i = 0; i < n - 1; i++) {17            for (int[] e : edges) {18                if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {19                    dist[e[1]] = dist[e[0]] + e[2];20                }21            }22        }23
24        // One more pass: any improvement means a negative cycle25        boolean hasNegativeCycle = false;26        for (int[] e : edges) {27            if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {28                hasNegativeCycle = true;29            }30        }31
32        System.out.println("Distances from 0: " + Arrays.toString(dist));33        System.out.println("Negative cycle: " + hasNegativeCycle);34    }35}

1#include <iostream>2#include <vector>3
4struct Edge {5    int from, to, weight;6};7
8int main() {9    const int INF = 1000000000;10    const int n = 5;11    std::vector<Edge> edges = {12        {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},13        {1, 4, -4}, {3, 4, 9}, {2, 1, -2},14    };15    std::vector<int> dist(n, INF);16    dist[0] = 0;17    // Relax every edge V-1 times18    for (int pass = 0; pass < n - 1; ++pass) {19        for (const Edge& e : edges) {20            if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {21                dist[e.to] = dist[e.from] + e.weight;22            }23        }24    }25    // One extra pass: any improvement means a negative cycle26    bool negativeCycle = false;27    for (const Edge& e : edges) {28        if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {29            negativeCycle = true;30        }31    }32    if (negativeCycle) {33        std::cout << "Negative cycle detected\n";34    } else {35        for (int v = 0; v < n; ++v) {36            std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";37        }38    }39    return 0;40}

1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7typedef struct {8    int from, to, weight;9} Edge;10
11int main(void) {12    Edge edges[] = {13        {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},14        {1, 4, -4}, {3, 4, 9}, {2, 1, -2},15    };16    int m = sizeof(edges) / sizeof(edges[0]);17    int dist[N];18    for (int v = 0; v < N; v++) dist[v] = INF;19    dist[0] = 0;20    // Relax every edge V-1 times21    for (int pass = 0; pass < N - 1; pass++) {22        for (int i = 0; i < m; i++) {23            Edge e = edges[i];24            if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {25                dist[e.to] = dist[e.from] + e.weight;26            }27        }28    }29    // One extra pass: any improvement means a negative cycle30    bool negativeCycle = false;31    for (int i = 0; i < m; i++) {32        Edge e = edges[i];33        if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {34            negativeCycle = true;35        }36    }37    if (negativeCycle) {38        printf("Negative cycle detected\n");39    } else {40        for (int v = 0; v < N; v++) {41            printf("Distance 0 -> %d: %d\n", v, dist[v]);42        }43    }44    return 0;45}