天天看點
傳回

單源最短路(優化篇之Dijkstra) 最短路（hdu2544)

最短路（hdu2544)

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 104625 Accepted Submission(s): 44973

1.Problem Description：

在每年的校賽裡，所有進入決賽的同學都會獲得一件很漂亮的t-shirt。但是每當我們的從業人員把上百件的衣服從商店運回到賽場的時候，卻是非常累的！是以現在他們想要尋找最短的從商店到賽場的路線，你可以幫助他們嗎？

Input:輸入包括多組資料。每組資料第一行是兩個整數N、M（N<=100，M<=10000），N表示成都的大街上有幾個路口，标号為1的路口是商店所在地，标号為N的路口是賽場所在地，M則表示在成都有幾條路。N=M=0表示輸入結束。接下來M行，每行包括3個整數A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A與路口B之間有一條路，我們的從業人員需要C分鐘的時間走過這條路。

輸入保證至少存在1條商店到賽場的路線。

Output:對于每組輸入，輸出一行，表示從業人員從商店走到賽場的最短時間

Sample Input

2 1

1 2 3

3 3

1 2 5

2 3 5

3 1 2

0 0

Sample Output

3

2

2.基本思路

這道題由于隻有100個城市，是以不采用任何優化，隻采用最簡單的Dijkstra便能通過。但為了能夠了解Dijkstra的主要優化方法我們以該題為例在該題的基礎上不斷地進行優化，最終達到終極版本，當你掌握了終極版本的Dijkstra算法之後，你将對Dijkstra問題無所畏懼。

3.代碼實作

3.1 v e r s i o n − 1 version-1 version−1 裸Dijkstra算法【采用鄰接連結清單和鄰接矩陣進行存取均可，當圖較為稀疏的時候采用鄰接連結清單效率更高，但圖較為稠密的時候采用鄰接矩陣的效率更高，但一般情況下鄰接連結清單的效率均更優】

#include <iostream>
#include <climits>
#include <vector>
#define N 101
using namespace std;

int dis[N];
int vis[N];

struct Next{
    int city;
    int time;
    Next(int _city,int _time){
        city = _city;
        time = _time;
    }
};

vector<Next> Vec[N];

int main()
{
    int n,m;
    int A,B,C;

    while(cin>>n>>m){

        if(n==0&&m==0)
            break;

        //init
        for(int i=1;i<=n;i++)
            dis[i]=-1,vis[i]=-1,Vec[i].clear();

        for(int i=0;i<m;i++){
            cin>>A>>B>>C;
            Vec[A].push_back(Next(B,C));
            Vec[B].push_back(Next(A,C));
        }

        int newP = 1;
        dis[newP] = 0;
        vis[newP] = 0;

        //dijkstra
        for(int i=0;i<n-1;i++){
            for(int j=0;j<Vec[newP].size();j++){
                int city = Vec[newP][j].city;
                int time = Vec[newP][j].time;
                if(vis[city]==0)
                    continue;
                if(dis[city]==-1||dis[city]>dis[newP]+time){
                    dis[city] = dis[newP]+time;
                }
            }

            int Min = INT_MAX;
            for(int j=1;j<=n;j++){
                if(vis[j]!=0){
                    if(~dis[j]){
                        if(dis[j]<Min){
                            Min=dis[j];
                            newP = j;
                        }
                    }
                }
            }

            vis[newP] = 0;
        }
        cout<<dis[n]<<endl;
    }
    return 0;
}

首先送出一發，好了，這就是我們優化的起點

單源最短路(優化篇之Dijkstra) 最短路（hdu2544)

3.2 v e r s i o n − 2 version-2 version−2 仔細想想，其實Dis[…]的更新并不一定是按順序的，是以我們隻需要在dis[N]更新完之後便可以得到最終個正确答案了。

#include <iostream>
#include <climits>
#include <vector>
#define N 101
using namespace std;

int dis[N];
int vis[N];

struct Next{
    int city;
    int time;
    Next(int _city,int _time){
        city = _city;
        time = _time;
    }
};

vector<Next> Vec[N];

int main()
{
    int n,m;
    int A,B,C;

    while(cin>>n>>m){

        if(n==0&&m==0)
            break;

        //init
        for(int i=1;i<=n;i++)
            dis[i]=-1,vis[i]=-1,Vec[i].clear();

        for(int i=0;i<m;i++){
            cin>>A>>B>>C;
            Vec[A].push_back(Next(B,C));
            Vec[B].push_back(Next(A,C));
        }

        int newP = 1;
        dis[newP] = 0;
        vis[newP] = 0;

        //dijkstra
        for(int i=0;i<n-1;i++){
            for(int j=0;j<Vec[newP].size();j++){
                int city = Vec[newP][j].city;
                int time = Vec[newP][j].time;
                if(vis[city]==0)
                    continue;
                if(dis[city]==-1||dis[city]>dis[newP]+time){
                    dis[city] = dis[newP]+time;
                }
            }

            int Min = INT_MAX;
            for(int j=1;j<=n;j++){
                if(vis[j]!=0){
                    if(~dis[j]){
                        if(dis[j]<Min){
                            Min=dis[j];
                            newP = j;
                        }
                    }
                }
            }

            vis[newP] = 0;
            if(newP==n)break;
        }

        cout<<dis[n]<<endl;

    }
    return 0;
}

再送出一發！！

單源最短路(優化篇之Dijkstra) 最短路（hdu2544)

咦，好像沒什麼變化，估計是測試用例中特殊資料樣例比較少，别急，後面還有大招呢，我們繼續優化。

3.3 v e r s i o n − 3 version-3 version−3 是時候分析一下上面算法的時間複雜度了，一看過去兩層 f o r for for循環特别醒目，是以該算法的平均時間複雜度為 O ( n 2 ) O(n^2) O(n2)。我們來分析一下兩層 f o r for for循環，第一層指的是最多一共需要選擇除了起始點外的 n − 1 n-1 n−1個結點，是以這一層循環是至少需要的，不可簡化的，而第二層循環的目的呢，主要是為了取出目前 d i s [ . . . ] dis[...] dis[...]數組中沒有被通路過的城市中對應最小 d i s [ i ] dis[i] dis[i]的城市 i i i，是以其是一個求解最小值的過程，這裡我們就可以考慮采用小頂堆進行優化，這樣每次求最小值的時候，我們隻需要取出堆頂的元素即可。分析算法可知，堆中元素最多可以到達 M M M個，也就是邊的數量。是以該算法的時間複雜度為 O ( N l o g M ) O(NlogM) O(NlogM)

下面放出優化之後的代碼:

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#define N 101
using namespace std;

int dis[N];
int vis[N];

struct Node{
    int id;
    int cost;
    Node(int _id,int _cost){
        id = _id;
        cost = _cost;
    }
    operator < (const Node& ano)const{
        return cost > ano.cost;
    }
};

priority_queue<Node> Que;

struct Next{
    int city;
    int time;
    Next(int _city,int _time){
        city = _city;
        time = _time;
    }
};

vector<Next> Vec[N];

int main()
{
    int n,m;
    int A,B,C;

    while(cin>>n>>m){

        if(n==0&&m==0)
            break;
        while(!Que.empty())
            Que.pop();

        //init
        for(int i=1;i<=n;i++)
            dis[i]=-1,vis[i]=-1,Vec[i].clear();

        for(int i=0;i<m;i++){
            cin>>A>>B>>C;
            Vec[A].push_back(Next(B,C));
            Vec[B].push_back(Next(A,C));
        }

        int newP = 1;
        dis[newP] = 0;
        vis[newP] = 0;

        //dijkstra
        for(int i=0;i<n-1;i++){
            for(int j=0;j<Vec[newP].size();j++){

                int city = Vec[newP][j].city;
                int time = Vec[newP][j].time;
                if(vis[city]==0)
                    continue;
                if(dis[city]==-1||dis[city]>dis[newP]+time){
                    dis[city] = dis[newP]+time;
                    Que.push(Node(city,dis[city]));
                }
            }

            while(!Que.empty()){

                if(vis[Que.top().id]!=-1){
                    Que.pop();
                    continue;
                }
                newP = Que.top().id;
                Que.pop();
                break;
            }

            vis[newP] = 0;
            if(newP==n)break;
        }

        cout<<dis[n]<<endl;

    }
    return 0;
}
單源最短路(優化篇之Dijkstra) 最短路（hdu2544)

3.4 v e r s i o n − 4 version-4 version−4 到這裡應該已經能過絕大部分的題目了，但仔細想想還有沒有優化的空間呢？有的，因為我們采用了vector來作為鄰接連結清單存儲圖的結構，而vector是STL封裝的進階資料結構，是以通路時間一般比簡單的整數數組來的慢，是以這裡可以采用鍊式前向星來存取整圖的結構，對于卡常的代碼還是值得嘗試采用該種方法來試一試。先貼出代碼和運作結果：

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#include <memory.h>
#define N 101
#define M 10001
using namespace std;

struct Node{
    int id;
    int cost;
    Node(int _id,int _cost){
        id = _id;
        cost = _cost;
    }
    operator < (const Node& ano)const{
        return cost > ano.cost;
    }
};

struct Edge{
    int next;//下條同起點的邊的編号
    int to;//該邊的終止點的編号
    int w;//該邊所具有的權重
}edge[M];

priority_queue<Node> Que;

int dis[N];
int vis[N];
int head[N];
int tot;

void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
}

void add_Edge(int u,int v,int w){
    edge[tot].to=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot++;
}

int main()
{
    int n,m;
    int A,B,C;

    while(cin>>n>>m){
        //init
        init();
        for(int i=1;i<=n;i++)
            vis[i]=0,dis[i]=0x3f3f3f3f;

        if(n==0&&m==0)
            break;

        while(!Que.empty())
            Que.pop();


        for(int i=0;i<m;i++){
            cin>>A>>B>>C;
            add_Edge(A,B,C);
            add_Edge(B,A,C);
        }

        int newP = 1;
        dis[newP] = 0;
        vis[newP] = 1;

        //dijkstra
        for(int i=0;i<n-1;i++){
            for(int j=head[newP];~j;j=edge[j].next){
                int city = edge[j].to;
                int time = edge[j].w;
                if(vis[city]!=1&&dis[city]>dis[newP]+time){
                    dis[city] = dis[newP]+time;
                    Que.push(Node(city,dis[city]));
                }
            }

            while(!Que.empty()){

                if(vis[Que.top().id]!=0){
                    Que.pop();
                    continue;
                }
                newP = Que.top().id;
                Que.pop();
                break;
            }

            vis[newP] = 1;
            if(newP==n)break;
        }

        cout<<dis[n]<<endl;
    }
    return 0;
}
單源最短路(優化篇之Dijkstra) 最短路（hdu2544)

最終運作的時間沒有多大的變化，主要還是該問題的資料規模比較小，但規模比較大的時候效果就比較明顯了。

關于前向星有以下兩篇文章值得參考：

https://blog.csdn.net/acdreamers/article/details/16902023

https://blog.csdn.net/lookqaq/article/details/81304637

最後為了證明優化的意義，不凡請各位看官移步hdu3790親自感受一下優化的魅力之所在。

以下是我最終AC的代碼：https://paste.ubuntu.com/p/gtW7ypFhRG/

4.Summary：

最後讓我們一起來總結一下，這篇文章的優化過程，首先我們采用了裸Dijkstra的代碼直接跑通，随後觀察到可以判斷終點的更新來提前終止算法，接下來我們分析了前面算法的時間複雜度，采用小頂堆來選取最小距離的結點将複雜度從 O ( n 2 ) O(n^2) O(n2)直接降到了 O ( N l o g M ) O(NlogM) O(NlogM)。最後，我們考慮采用鍊式前向星來優化圖的存儲，相比于Vector資料結構存儲圖，其通路圖中邊的效率得到了提高，以上。

算法刷題集 最短路 dijkstra 優化
上一篇: 開發環境使用nodemon --in
下一篇: Codeforces Round #269 (Div. 2)（D. MUH and Cube Walls（KMP））

繼續閱讀