Bellman-Ford算法能在一般情況下(存在負權邊的情況)下,解決單源最短路問題。同時可以檢測圖中是否存在着一個從源點可達的權和為負的回路。若存在這樣的回路的話,算法說明該問題誤解;若不存在,算法将産生最短路徑及其權值。
基于鄰接矩陣實作:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAX_VAL 100000
#define MAX_NODE 100
int G[MAX_NODE][MAX_NODE];
int d[MAX_NODE];
int path[MAX_NODE];
int s;
bool bellman_ford(int num)
{
for(int i = 0; i < num; i++)
{
d[i] = MAX_VAL;
path[i] = -1;
}
d[s] = 0;
for(int k = 1; k <= num - 1; k++)
{
for(int i = 0; i < num; i++)
{
if(d[i] == MAX_VAL)
continue;
for(int j = 0; j < num; j++)
{
if(G[i][j] == -1)
continue;
if(d[j] > d[i] + G[i][j])
{
d[j] = d[i] + G[i][j];
path[j] = i;
}
}
}
}
for(int i = 0; i < num; i++)
{
for(int j = 0; j < num; j++)
{
if(G[i][j] == -1)
continue;
if(d[j] > d[i] + G[i][j])
return false;
}
}
return true;
}
void print_path(int o)
{
if(o == s)
{
printf("%d ", o);
return;
}
print_path(path[o]);
printf("%d ", o);
}
int main()
{
/* code */
memset(G, -1, MAX_NODE * MAX_NODE * sizeof(int));
int num = 7;
G[0][1] = 2;
G[0][3] = 1;
G[1][3] = 3;
G[1][4] = 10;
G[2][0] = 4;
G[2][5] = 5;
G[3][2] = 2;
G[3][4] = 2;
G[3][5] = 8;
G[3][6] = 4;
G[4][6] = 6;
G[6][5] = 1;
s = 0;
bool flag = bellman_ford(num);
if(flag == false)
printf("%s\n", "Has negtive circle!");
else
{
int o = 5;
printf("The shortest path is: %d\n", d[o]);
print_path(o);
}
return 0;
}
基于鄰接表實作:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAX_VAL 100000
#define MAX_NODE 100
struct node
{
struct node *next;
int node_label;
int weight;
void init(int label, int w, struct node *n)
{
node_label = label;
weight = w;
next = n;
}
};
struct node * G[MAX_NODE];
int d[MAX_NODE];
int path[MAX_NODE];
int s;
bool bellman_ford(int num)
{
struct node *tmp;
for(int i = 0; i < num; i++)
{
d[i] = MAX_VAL;
path[i] = -1;
}
d[s] = 0;
for(int k = 1; k <= num - 1; k++)
{
for(int i = 0; i < num; i++)
{
if(d[i] == MAX_VAL)
continue;
tmp = G[i];
while(tmp != NULL)
{
if(d[tmp->node_label] > d[i] + tmp->weight)
{
d[tmp->node_label] = d[i] + tmp->weight;
path[tmp->node_label] = i;
}
tmp = tmp->next;
}
}
}
for(int i = 0; i < num; i++)
{
tmp = G[i];
while(tmp != NULL)
{
if(d[tmp->node_label] > d[i] + tmp->weight)
return false;
tmp = tmp->next;
}
}
return true;
}
void print_path(int o)
{
if(o == s)
{
printf("%d ", o);
return;
}
print_path(path[o]);
printf("%d ", o);
}
int main()
{
for(int i = 0; i < MAX_NODE; i++)
G[i] = NULL;
int num = 7;
struct node *tmp1, *tmp2, *tmp3, *tmp4;
tmp1 = new struct node;
tmp1->init(1, 2, NULL);
tmp2 = new struct node;
tmp2->init(3, 1, tmp1);
G[0] = tmp2;
tmp1 = new struct node;
tmp1->init(3, 3, NULL);
tmp2 = new struct node;
tmp2->init(4, 10, tmp1);
G[1] = tmp2;
tmp1 = new struct node;
tmp1->init(0, 4, NULL);
tmp2 = new struct node;
tmp2->init(5, 5, tmp1);
G[2] = tmp2;
tmp1 = new struct node;
tmp1->init(2, 2, NULL);
tmp2 = new struct node;
tmp2->init(4, 2, tmp1);
tmp3 = new struct node;
tmp3->init(5, 8, tmp2);
tmp4 = new struct node;
tmp4->init(6, 4, tmp3);
G[3] = tmp4;
tmp1 = new struct node;
tmp1->init(6, 6, NULL);
G[4] = tmp1;
G[5] = NULL;
tmp1 = new struct node;
tmp1->init(5, 1, NULL);
G[6] = tmp1;
s = 0;
bool flag = bellman_ford(num);
if(flag == false)
printf("%s\n", "Has negtive circle!");
else
{
int o = 5;
printf("The shortest path is: %d\n", d[o]);
print_path(o);
}
delete(tmp1);
delete(tmp2);
delete(tmp3);
delete(tmp4);
return 0;
}