《啊哈！算法》之最短路徑（Dijkstra算法和bellman-ford算法及其隊列優化）

最短路徑

• Dijkstra
• Bellman-Ford

Dijkstra

該算法的基本思想為：

每次找到離源點最近的一個頂點，然後以該頂點為中心進行擴充最終得到源點到其餘所有點的最短路徑。

基本步驟如下：

1. 将所有頂點分為兩部分：已知最短路程的頂點集合P和未知最短路程的頂點集合Q。用book[i]表示，如果book[i]=1則表示這個頂點在集合P中，反之頂點在集合Q中。
2. 設定源點s到自己的最短路徑為0。其餘按照實際情況進行設定。
3. 在集合Q的所有定點中選擇一個離源點s最近的頂點加入到集合P。并考察所有以點u為起點的邊，對每一條邊進行松弛操作。
4. 重複第三步，如果集合Q為空，算法結束。最終dis數組中的值就是源點到所有頂點的最短路徑。

#include<iostream>
using namespace std;
#define MAX 999999
int main ()
{
    int book[],e[][],dis[];    //book[i]=0表示在未确定最小路徑的集合中，book[i]=1表示在确定最小路徑的集合中
    int s,n,m;
    int a,b,c;
    int i,j,u;
    cout << "please input the number of the  city: ";
    cin >> n;
    cout << "is there how many roads: ";
    cin >> m;
    cout << "please input the start: ";
    cin >> s;
    for(int i =;i<=n;++i)
    {
        for(int j=;j<=n;++j)
        {
            if(i == j)
            {
                e[i][j]=;
            }
            else
                e[i][j]=MAX;
        }
    }
    cout << "please input the information of the roads: ";
    for(int k=;k<=m;++k)
    {
         cin >> a >> b >> c;
         e[a][b]=c;
    }
    for(i=;i<=n;++i)
        dis[i]=e[s][i];
    for(i=;i<=n;++i)
        book[i]=;
    book[s]=;
    for(int k=;k<=n-;++k)                //要去找n-1次，因為最多包含n-1次松弛    //算法的核心代碼
    {
        for(j=;j<=n;++j)
        {
            int minute=MAX;
            if((book[j] ==) && (dis[j]< minute))    //确定相鄰城市的中距離最小的是哪個
            {
                minute = dis[j];
                u=j;
            }
        }
        book[u]=;
        for(i=;i<=n;++i)
        {
            if(e[u][i]<MAX)                
            {
                if(dis[i]>(dis[u]+e[u][i]))    //将路徑松弛
                    dis[i]=dis[u]+e[u][i];
            }
        }
    }
    for(i=;i<=n;++i)
        cout << dis[i]<<" ";
    return ;
}
           

Bellman-Ford及其隊列優化

#include<iostream>
using namespace std;
#define MAX 999999

int main()
{
    int u[],v[],w[],dis[];
    int s,n,m;
    int k,i;
    cout << "please input the number of the  city: ";
    cin >> n;
    cout << "is there how many roads: ";
    cin >> m;
    cout << "please input the start: ";
    cin >> s;
    cout << "please input the information of the roads: ";
    for(k=;k<=m;++k)
    {
        cin >> u[k] >> v[k] >> w[k];
    }
    for(i=;i<=n;++i)
        dis[i]=MAX;
    dis[s]=;
    for(k=;k<=n-;++k)    //進行n-1輪松弛
    {
        for(i=;i<=n;++i)   //枚舉每一條邊
        {
            if(dis[v[i]]>(dis[u[i]]+w[i]))    //對每一條邊進行松弛
                dis[v[i]]=dis[u[i]]+w[i];
                //dis[1][v[i]] = dis[u[i]] + w[i];
        }
    }
    for(i=;i<=n;++i)
        cout << dis[i] << " ";
    return ;
}
           

上述代碼中，外循環一共循環了n-1次（n為頂點的個數），内循環循環了m次（m為邊的個數），即枚舉每一條邊。dis數組的作用與Dijkstra算法一樣，是用來記錄源點到其餘各個頂點的最短路徑。u、v合w三個數組是用來記錄邊的資訊。

隊列優化

隊列優化最核心的思想就是：

每次僅對最短路徑估計值發生了變化的頂點的所有出邊執行松弛操作。

每次選取隊首頂點u，對頂點的所有出邊進行松弛操作。例如有一條u→v的邊，如果通過u→v這條邊是的源點到頂點v的最短路程變短，且頂點v不在目前的隊列中，就将頂點v放入隊尾。需要注意的是，同一個頂點同時在隊列中出現多次是毫無意義的，是以我們需要一個數組來判重。在對頂點u的所有出邊松弛完畢後，就将頂點u出隊。

#include<iostream>
using namespace std;
#define INF 999999

int main ()
{
    int dis[],que[]={},book[];
    int first[],next[];
    int u[],v[],w[];
    int head=,tail=;
    int s,n,m,i;
    cout << "please input the number of the  city: ";
    cin >> n;
    cout << "is there how many roads: ";
    cin >> m;
    cout << "please input the start: ";
    cin >> s;
    cout << "please input the information of the roads: ";
    for(i=;i<=n;++i)
        dis[i]=INF;
    dis[s]=;
    for(i=;i<=n;++i)
        book[i]=;
    for(i=;i<=n;++i)
        first[i]=-;
    for(i=;i<=m;++i)
    {
        cin >> u[i] >> v[i] >> w[i];
        next[i]=first[u[i]];
        first[u[i]]=i;
    }
    que[tail]=s;
    ++tail;
    book[s]=;
    while(head < tail)
    {
        int k;
        k=first[que[head]];
        while(k != -)
        {
            if(dis[v[k]]>(dis[u[k]]+w[k]))
            {
                dis[v[k]]=dis[u[k]]+w[k];
                if(book[v[k]] == )
                {
                    que[tail]=v[k];
                    ++tail;
                    book[v[k]]=;
                }
            }
            k=next[k];
        }
        book[que[head]]=;
        ++head;
    }
    for(i=;i<=n;++i)
        cout << dis[i] << " ";
    return ;
}