http://www.csanimated.com/animation.php?t=Bellman-Ford_algorithm
1 procedure BellmanFord(list vertices, list edges, vertex source)
2 // This implementation takes in a graph, represented as lists of vertices
3 // and edges, and modifies the vertices so that their distance and
4 // predecessor attributes store the shortest paths.
5
6 // Step 1: Initialize graph
7 for each vertex v in vertices:
8 if v is source then v.distance := 0
9 else v.distance := infinity
10 v.predecessor := null
11
12 // Step 2: relax edges repeatedly
13 for i from 1 to size(vertices)-1:
14 for each edge uv in edges: // uv is the edge from u to v
15 u := uv.source
16 v := uv.destination
17 if v.distance > u.distance + uv.weight:
18 v.distance := u.distance + uv.weight
19 v.predecessor := u
20
21 // Step 3: check for negative-weight cycles
22 for each edge uv in edges:
23 u := uv.source
24 v := uv.destination
25 if v.distance > u.distance + uv.weight:
26 error "Graph contains a negative-weight cycle"
27
An implementation from wiki
1 #include <limits.h>
2 #include <stdio.h>
3 #include <stdlib.h>
4
5 /* Let INFINITY be an integer value not likely to be
6 confused with a real weight, even a negative one. */
7 #define INFINITY ((1 << 14)-1)
8
9 typedef struct {
10 int source;
11 int dest;
12 int weight;
13 } Edge;
14
15 void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
16 {
17 int *distance = malloc(nodecount * sizeof *distance);
18 int i, j;
19
20 for (i=0; i < nodecount; ++i)
21 distance[i] = INFINITY;
22 distance[source] = 0;
23
24 for (i=0; i < nodecount; ++i) {
25 int somethingchanged = 0;
26 for (j=0; j < edgecount; ++j) {
27 if (distance[edges[j].source] != INFINITY) {
28 int new_distance = distance[edges[j].source] + edges[j].weight;
29 if (new_distance < distance[edges[j].dest]) {
30 distance[edges[j].dest] = new_distance;
31 somethingchanged = 1;
32 }
33 }
34 }
35 /* if one iteration had no effect, further iterations will have no effect either */
36 if (!somethingchanged) break;
37 }
38
39 for (i=0; i < edgecount; ++i) {
40 if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {
41 puts("Negative edge weight cycles detected!");
42 free(distance);
43 return;
44 }
45 }
46
47 for (i=0; i < nodecount; ++i) {
48 printf("The shortest distance between nodes %d and %d is %d\n",
49 source, i, distance[i]);
50 }
51
52 free(distance);
53 return;
54 }
55
56 int main(void)
57 {
58 /* This test case should produce the distances 2, 4, 7, -2, and 0. */
59 Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},
60 {2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},
61 {4,0, 6}, {4,2, 7}};
62 BellmanFord(edges, 10, 5, 4);
63 return 0;
64 }