算法——最短路徑——Bellman-Ford算法

Bellman-Ford算法

作用：求源點到其他所有點的最短路徑，可以處理存在負環的情況

時間複雜度：O(V*E) //V為頂點數，E為邊數

原理：

1.用Distans[i]記錄源點s到i的距離，首先初始化Distanc，如果存在s到i的邊則設Distans[i]=si，如果不存在，則設Distans[i]=無窮，Distans[s]=0。

2.對于n個頂點中的每個頂點u，檢測其對于每一條邊uv，Distant[u] + w(u, v) < Distant[v]，則另Distant[v] = Distant[u]+w(u, v)。w(u, v)為邊e(u,v)的權值。

3.為了檢測圖中是否存在負環路，即權值之和小于0的環路。對于每一條邊e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的邊，則圖中存在負環路，即是說改圖無法求出單源最短路徑。否則數組Distant[n]中記錄的就是源點s到各頂點的最短路徑長度。

c代碼實作

#include<stdio.h>
#include<stdlib.h>
const int maxnum = ;
const int maxint = ; 
// 邊
typedef struct Edge{
    int u, v;    // 起點，終點點
    int weight;  // 邊的權值
}Edge;

Edge edge[maxnum];     // 儲存所有邊的值
int  dist[maxnum];     // 結點到源點最小距離

int nodenum, edgenum, source;    // 結點數，邊數，源點


void init()
{
    // 輸入結點數，邊數，源點
    scanf("%d%d%d",&nodenum,&edgenum,&source);
    for(int i=; i<=nodenum; ++i)
        dist[i] = maxint;
    dist[source] = ;
    for(int i=; i<=edgenum; ++i)
    {
        scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].weight);
        if(edge[i].u == source)          //注意這裡設定初始情況
            dist[edge[i].v] = edge[i].weight;
    }
}

// 松弛計算
void relax(int u, int v, int weight)
{
    if(dist[v] > dist[u] + weight)
        dist[v] = dist[u] + weight;
}

 bool Bellman_Ford()
{
    for(int i=; i<=nodenum-; ++i)
        for(int j=; j<=edgenum; ++j)
            relax(edge[j].u, edge[j].v, edge[j].weight);
    bool flag = ;
    // 判斷是否有負環路
    for(int i=; i<=edgenum; ++i)
        if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)
        {
            flag = ;
            break;
        }
    return flag;
}
int main(){
    init();
    if(Bellman_Ford())
        for(int i =  ;i <= nodenum; i++)
            printf("%d\n",dist[i]);
    return ;
}