1霹陡、基本思想
它是最優(yōu)性原理的直接應(yīng)用富寿，算法基于以下事實(shí)：
（1）如果最短路徑存在导披，則每個頂點(diǎn)最多經(jīng)過一次，因此不超過n-1條邊窍仰。
（2）長度為k的路徑由長度為k-1的路加一條邊得到疼约。
（3）由最優(yōu)性原理躬窜，只需依次考慮長度為1,2捞高，...，k-1的最短路徑甸私。
2猪勇、步驟
對每條邊邊進(jìn)行|V|-1次Relax(松弛)操作。
如果存在（u颠蕴，v）屬于E泣刹，使得dis[u]+w<dis[v],則存在負(fù)權(quán)回路；否則dis[v]即為s到v的最短距離犀被，pre[v]為前驅(qū)椅您。
Bell-Ford實(shí)質(zhì)上就是一個迭代處理過程。
3寡键、樣例代碼
//Bellman-Ford map[i][j]==MaxInt means no direct path from i to j
void bellman_ford() {
bool notfinish=false;
memset(checked,0,sizeof(checked));
checked[s]=true;
for(k=0; k<n&&!notfinish; k++) {
notfinish=true;
for(i=0; i<n; i++) {
}
}
}
