-
Notifications
You must be signed in to change notification settings - Fork 4
/
Bellman-Ford.c
49 lines (42 loc) · 1.08 KB
/
Bellman-Ford.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
* =====================================================================================
* Filename: Bellman-Ford.c
* Description:
* Version: 1.0
* Created: 2014Äê01ÔÂ08ÈÕ 22ʱ08·Ö53Ãë
* Author: wuyue (wy), vvuyve@gmail.com
* Company: UESTC
* =====================================================================================
*/
#include "graph.h"
int Bellman_Ford(GraphL *g,int s,GVDis* GVDisTable)
{
int i,j;
GVDis_init(g,s,GVDisTable);
GVLNode *p;
for(i=1;i <= g->nV-1;i++)
{
for(j=0;j<g->nV;j++)
{
p = g->adjlist + j;
p = p->next;
while(p!=NULL)
{
Relax(g,j,p->vertex,p->weight,GVDisTable);
p = p->next;
}
}
}
for(j=0;j<g->nV;j++)
{
p = g->adjlist + j;
p = p->next;
while(p!=NULL)
{
if(GVDisTable[p->vertex].distance > GVDisTable[j].distance + p->weight)
return 0;
p = p->next;
}
}
return 1;
}