posts - 100,  comments - 15,  trackbacks - 0
 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,15}{0,28}{0,3-4}{1,0-2},
66                      {2,1-3}{2,39}{3,17}{3,42},
67                      {4,06}{4,27}}
;
68    BellmanFord(edges, 1054);
69    return 0;
70}

71
posted on 2009-04-03 22:08 wyiu 阅读(193) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理