一、最短路是什么？

最短路演算法其實有很多種：

1.Dijkstra（迪杰斯特拉） 演算法

2.多源最短路

鄙人不才，今天先收錄使用臨接矩陣和佇列實作Dij演算法，其他的演算法以后再做補充······

今天有好多同學反應說是最短路代碼單看看不懂，確實是這樣，當初我學習的時候也看了一晚上一頭霧水，今天添加一些便于理解的注釋，希望能幫助到大家少走彎路

二、演算法介紹？

（狄克斯特拉1930年5月11日生于荷蘭鹿特丹的一個知識分子家庭，在兄弟姊妹4人中排行第三，他的父親是一名化學家和發明家，曾擔任荷蘭化學會主席，他母親則是一位數學家，他成功地設計并實作了在有障礙物的兩個地點之間找出一條最短路徑的高效演算法，這個演算法被命名為“狄克斯特拉演算法”，解決了機器人學中的一個十分關鍵的問題，即運動路徑規劃問題，至今仍被廣泛應用，被認為是利用“貪心法”(greedy method)設計演算法的一個成功范例，）
完整演算法的圖：

我們這里定義圖的編號為：

1 2 3

4 5 6

7 8 9

圖1：初始化的圖，其中包含邊的權值（耗時），（這里圖是有向圖），

圖2：確定起點，然后向能直接走到的點走一下，記錄此時的估計值：2 6 9.，

圖3：找到距離起點最近的點，是正東邊的那個點，這時候我們耗費權值為2，然后我們進行松弛操作，從起點到其東南方的點直接到的權值耗費為6，但是我們通過剛剛選定的點，我們找到了到這個點更近的方式，所以這個時候我們說從起點到其東南方向的點的權值更新值從6變成了5，這個時候我們就完成了第一次松弛操作，

圖4：依舊是找距離起點最近的點，然后松弛我們發現這個時候從起點到其東南方的點的耗費權值從5又變成了4.這個時候我們完成了第二個松弛，

之后的方式同上：選定距離起點最近的點v，然后通過點v進行松弛操作，我們發現能夠通過增加走到目的地方式的復雜度（多轉彎）的方式我們能夠松弛掉權值，使得耗費的權值更小，

三、演算法演示

首先第一步，我們先要把所有的資料讀到程式里，那么用什么辦法來存盤路徑資料呢？
聰明的你肯定想到了（maybe？），我們可以用臨階矩陣實作，也就是說，建立一個二維的陣列，
存資料的時候，比如說這道題，給你的資料會是：

6 8
1 6 100
1 5 30 
4 6 10
1 3 10
2 3 5
3 4 50
5 4 20
5 6 60

這里的6表示6個結點，8表示會有8組資料
下面的8組資料前兩個是節點，第三個是權值
我們把前兩個資料作為map（二維資料）的橫縱坐標，第三個資料作為存的值
（這里有有向圖和無向圖的區別，如果是無向圖我們需要雙向導通，具體操作看代碼）
另外，記得把i==j的資料標為0（本身到本身距離為0）

第二步，我們申明一個dis陣列，用來存放從V1到各個頂點距離的資料
（這里注意，題目不一樣需求也不一樣，可能問的是其他點到某點的距離，這個靈活變通好伐）

顯然呢，我們可以根據本題得到dis初始值為[0,INF,10,INF,30,100]

這里有幾點可能容易引起困惑，第一個0指的是從1到1的距離，顯然是0（本身到本身），你可以把這個看成是一個1*6的矩陣，縱坐標表示的就是1，2，3，4，5，6，這樣我們就將能從1直接到某處的距離標記了下來

接下來進行查找的操作，我們要從這個dis里找到最短的路徑，顯然是從1到3的距離是10，我們把這個距離送到min里，如何flag=3，作為之后vis訪問過的依據（vis[flag] = 1）

之后呢，回到我們剛才建立好的圖，我們從flag行開始尋找，看一下此時flag行的資料，我們可以知道是[10,5,0,50,0,0],然后列從1到6跑一個回圈，判斷條件是（map[flag][j]+min<dis[j]），這個條件就是判斷從3開始到別的地方的路程加上從v1到v3的路程是不是小于從v1到某處的路，如果是的話很顯然將dis[j]用map[flag][j]+min<dis[j]覆寫掉就可以了
跑完這個回圈，dis也更新成了[0,15,10,60,30,100]

就這樣，dis的值不斷的變化，最終我們得到的結果就是從v1到任意一點的最短路徑，是不是很簡單呢？

四、題目示例

1.模版題（ZCMU-1624）

鏈接: ZCMU-1624.
1624: 最短路
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 368 Solved: 99
[Submit][Status][Web Board]
Description
有n個城市編號為1—n，m條路，告訴你每條路的長度，求給定兩點的最短路徑長度，

Input
T 組資料

每組資料第一行有兩個正整數n,m（n<=1000,m<=10000）分別表示城市的數量和路的條數，接下來m行，每行3個整數a,b,c，表示城市a和城市b之間有一條c長度的路

最后一行輸入兩個整數x,y，

Output
輸出城市 x 到城市 y 的最短路徑，如果不存在輸出-1，

Sample Input
2
3 2
1 2 2
2 3 3
1 3
4 2
1 2 3
1 3 2
1 4
Sample Output
5
-1

2.實作代碼

代碼如下（示例）：

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
int main(){
    int map[1005][1005],vis[1005],dis[1005];
    int T;
    cin >> T;
    int n,m;
    int a,b,h;
    while(T--){
        memset(vis, 0, sizeof vis);
        cin >> n >> m;
        //這里在初始化，就是將map的任意一點的距離都設定為無窮
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        map[i][j] = INF;
            
        
        for(int i =1;i<=n;i++)
        map[i][i] = 0;
        for(int i =1;i<=m;i++){
            cin >> a >> b >> h;
            if(h<map[a][b]){
            //雙向導通
            map[a][b] = h;
            map[b][a] = h;
            }
        }

//        cout << endl;
//        for(int i=1;i<=n;i++){
//        for(int j=1;j<=n;j++)
//        cout << map[i][j] << " ";
//        cout << endl;
//        }


        int st,nd;
        scanf("%d %d",&st,&nd);
        for(int i =1;i<=n;i++)dis[i] = map[st][i];
        for(int i=1;i<n;i++){
            int min = INF;
            int flag = 0;
            for(int j=1;j<=n;j++){
            //這里就是查找最短的距離
                if(min>dis[j]&&!vis[j]){
                    flag = j;
                    min = dis[j];
                }
            }
            vis[flag] = 1;
            for(int j=1;j<=n;j++){
            //判斷并且覆寫
                if(min+map[flag][j]<dis[j]&&!vis[j])
                    dis[j] = min + map[flag][j];
            }
        }
        int temp = dis[nd];
        if(temp!=INF)
            printf("%d\n",temp);
        else
            printf("-1\n");
//        for(int i=2;i<=n;i++)
//        cout << dis[i] << " ";
//        cout << endl;
    }
    return 0;
}

下面是一個從別人博客轉載的利用佇列實作的，貼在這里便于以后查看：

void spfa()
{
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0; vis[1] = 1;//vis記錄是否在佇列里 
	queue<int> q;
	q.push(1);
	register int u, v;
	while(q.size())
	{
		u = q.front(); q.pop(); vis[u] = 0;
		for(int i = head[u]; ~i; i = e[i].nxt)//向外發散 
		{
			v = e[i].to;
			if(dis[u] + e[i].w < dis[v])
			{
				dis[v] = dis[u] + e[i].w;
				if(!vis[v]) q.push(v), vis[v] = 1; //不在佇列中，那就放進去更新別的點 
			}
		}
	}
}

幾個需要注意的小點：
1.解題前需要判斷這是一個有向圖還是一個無向圖，在讀入資料的時候還是有差距的
2.值得注意的是，可能會出現找不到最短路徑的情況，也就是說，某地到某地的路程為無窮（maxn），此時記得輸出-1即可
3.這題有幾個變化，比如現在模版題是輸出x到y的最短路徑，有些時候可能只是叫你輸出從1到任意城市的最短路徑，這點知道一下就可以了

總結

提示：這里對文章進行總結：
最短路Dij演算法在ACM競賽中占重要地位，是一個需要熟記熟練使用的演算法，不熟的話多打幾次模版題就可以了，