這個(gè)算法實(shí)現(xiàn)比dijkstra+heap簡(jiǎn)單，但是時(shí)間效率低一些 (O(VE))。可以判斷是否有負(fù)權(quán)的環(huán)。
算法的基礎(chǔ)是單源最短路問(wèn)題中的path-relaxation property：設(shè)v_0到v_k的最短路為p={v_0, .... ,v_k}，若p被relax的順序是(v_0, v_1),...,(v_k-1,v_k)，則最后得到的v_0到p上各點(diǎn)的距離就是最短距離。
#include <iostream>
#define MAXN 200
#define INF 0xfffffff
using namespace std;
int list[MAXN][MAXN][2]; // 存儲(chǔ)圖,list[i][j][0]表節(jié)點(diǎn)編號(hào)，list[i][j][1]表節(jié)點(diǎn)i到list[i][j][0]的距離
int deg[MAXN]; // 各節(jié)點(diǎn)的出度
int n; // 節(jié)點(diǎn)數(shù)
int trace[MAXN]; // 存儲(chǔ)最短路
int d[MAXN]; // 算法結(jié)束時(shí)d[i]存源到節(jié)點(diǎn)i的最短距離
void initialize_single_source()
{
int i;
for(i=1;i<=n;i++) d[i]=INF;
d[1]=0;
}
void relax(int u,int v)
{
if(d[list[u][v][0]]>d[u]+list[u][v][1])
{
trace[list[u][v][0]]=u;
d[list[u][v][0]]=d[u]+list[u][v][1];
}
}
int bellman_ford()
{// 若存在負(fù)環(huán)返回-1；否則返回1
int i,j,k;
initialize_single_source();
for(i=0;i<n-1;i++)
{// 對(duì)所有邊relax n-1次
for(j=1;j<=n;j++)
{// 遍歷所有邊
for(k=0;k<deg[j];k++) relax(j,k);
}
}
// 檢查是否有負(fù)權(quán)的環(huán)
for(i=1;i<=n;i++)
{
for(j=0;j<deg[i];j++)
{
if(d[list[i][j][0]]>d[i]+list[i][j][1]) return -1;
}
}
//for(i=1;i<=n;i++) printf("%d distance:%d\n",trace[i],d[i]);
return 1;
}
void readdata()
{
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",°[i]);
for(j=0;j<deg[i];j++)
{
scanf("%d%d",&list[i][j][0],&list[i][j][1]);
}
}
}
int main()
{
freopen("test.txt","r",stdin);
readdata();
printf("%d",bellman_ford());
return 1;
}