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
9typedef struct 
{
10
int source;
11 int dest;
12 int weight;
13} Edge;
14
15void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
16{
17 int *distance = (int*) malloc (nodecount * sizeof (*distance)); //int
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
{
26 int somethingchanged = 0;
27 for (j=0; j < edgecount; ++j)
28 {
29 if (distance[edges[j].source] != INFINITY)
30 {
31 int new_distance = distance[edges[j].source] + edges[j].weight;
32 if (new_distance < distance[edges[j].dest])
33 {
34 distance[edges[j].dest] = new_distance;
35 somethingchanged = 1;
36
}
37 }
38 }
39 /**//* if one iteration had no effect, further iterations will have no effect either */
40 if (!somethingchanged) break;
41 }
42
43 for (i=0; i < edgecount; ++i)
44 {
45 if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight)
46 {
47 puts("Negative edge weight cycles detected!");
48 free(distance);
49 return;
50 }
51 }
52
53 for (i=0; i < nodecount; ++i) {
54 printf("The shortest distance between nodes %d and %d is %d\n",
55 source, i, distance[i]);
56 }
57
58 free(distance);
59 return;
60}
61
62int main(void)
63{
64 /**//* This test case should produce the distances 2, 4, 7, -2, and 0. */
65 Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},
66 {2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},
67 {4,0, 6}, {4,2, 7}};
68 BellmanFord(edges, 10, 5, 4);
69 return 0;
70}
71
posted on 2009-04-03 22:08
wyiu 閱讀(196)
評(píng)論(0) 編輯 收藏 引用