先簡單介紹一下最短路徑：
最短路徑是啥？就是一個帶邊值的圖中從某一個頂點到另外一個頂點的最短路徑。
官方定義：對于内網圖而言，最短路徑是指兩頂點之間經過的邊上權值之和最小的路徑。
并且我們稱路徑上的第一個頂點為源點，最後一個頂點為終點。
由于非内網圖沒有邊上的權值，所謂的最短路徑其實是指兩頂點之間經過的邊數最少的路徑。
我們時常會面臨着對路徑選擇的決策問題，例如在中國的一些一線城市如北京、上海、廣州、深圳等，一般從A點到到達B點都要通過幾次地鐵、公交的換乘才可以到達。
有些朋友想用最短對的時間，有些朋友想花最少的金錢，這就涉及到不同的方案，那麼如何才能最快的計算出最佳的方案呢？
最短路徑求法
在網圖和非網圖中，最短路徑的含義是不同的。
- 網圖是兩頂點經過的邊上權值之和最少的路徑。
- 非網圖是兩頂點之間經過的邊數最少的路徑。
我們把路徑起始的第一個頂點稱為源點，最後一個頂點稱為終點。
關于最短路徑的算法，我們會介紹以下算法：
- 迪傑斯特拉算法（Dijkstra）
求V0到V8的最短路徑
你找到了嗎
好了，我想你大概明白了，這個迪傑斯特拉算法是如何工作的。
它并不是一下子就求出了V0到V8的最短路徑，而是一步步求出它們之間頂點的最短路徑，過程中都是基于已經求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得到你要的結果。
迪傑斯特拉(Dijkstra)算法
1. 迪傑斯特拉(Dijkstra)算法簡介
迪傑斯特拉（dijkstra）算法是典型的用來解決最短路徑的算法，也是很多教程中的範例，由荷蘭計算機科學家狄克斯特拉于1959年提出，用來求得從起始點到其他所有點最短路徑。該算法采用了貪心的思想，每次都查找與該點距離最近的點，也因為這樣，它不能用來解決存在負權邊的圖。解決的問題大多是這樣的：有一個無向圖G(V,E)，邊E[i]的權值為W[i]，找出V[0]到V[i]的最短路徑。
2.迪傑斯特拉算法的原理
(附上小圖一張)
①首先，引入一個輔助向量D，它的每個分量D[i]表示目前所找到的 Dijkstra算法運作動畫過程 Dijkstra算法運作動畫過程 從起始點 （即源點 ）到其它每個頂點 的長度。例如，D[3] = 2表示從起始點到頂點3的路徑相對最小長度為2。這裡強調相對就是說在算法執行過程中D的值是在不斷逼近最終結果但在過程中不一定就等于長度。
②D的初始狀态為：若從v 到v[i]有弧（即從v到v[i]存在連接配接邊），則D[i]為弧上的權值（即為從v到v[i]的邊的權值）；否則置D[i]為∞。顯然，長度為 D[j]= Min{ D |v[i]∈V } 的路徑就是從v出發到頂點v[j]的長度最短的一條路徑，此路徑為(v,v[j])。
③那麼，下一條長度次短的是哪一條呢？也就是找到從源點v到下一個頂點的最短路徑長度所對應的頂點，且這條最短路徑長度僅次于從源點v到頂點v[j]的最短路徑長度。 假設該次短路徑的終點是v[k]，則可想而知，這條路徑要麼是(v,v[k])，或者是(v,v[j],v[k])。它的長度或者是從v到v[k]的弧上的權值，或者是D[j]加上從v[j]到v[k]的弧上的權值。
④一般情況下，假設S為已求得的從源點v出發的最短路徑長度的頂點的集合，則可證明：下一條次最短路徑（設其終點為x）要麼是弧(v,x)，或者是從源點v出發的中間隻經過S中的頂點而最後到達頂點 的路徑。 是以，下一條長度次短的的最短路徑長度必是D[j]= Min{ D[i] |v[i]∈V-S }，其中D 要麼是弧( v,v[i])上的權值，或者是D[i]( v[k]∈S)和弧(v[k] ,v[i] )上的權值之和。
3.迪傑斯特拉算法的實作過程
①先取一點v[0]作為起始點，初始化dis[i],d[i]的值為v[0]到其餘點v[i]的距離w[0][i]，如果直接相鄰初始化為權值，否則初始化為無限大；
②将v[0]标記，vis[0] = 1(vis一開始初始化為0)；
③找尋與v[0]相鄰的最近點v[k]，将v[k]點記錄下來，v[k]與v[0]的距離記為min；
④把v[k]标記，vis[k]=1；
⑤查詢并比較，讓dis[j]與min+w[k][j]進行比較，判斷是直接v[0]連接配接v[j]短，還是經過v[k]連接配接v[j]更短，即dis[j]=MIN(dis[j],min+w[k][j])；
⑥繼續重複步驟③與步驟⑤，知道找出所有點為止。
4.迪傑斯特拉的實作代碼（C/C++）
1 int Dijkstra(int n)
2 {
3 //初始化v[0]到v[i]的距離
4 for(int i=1;i<=n;i++)
5 dis[i]=w[0][i];
6 vis[0]=1;//标記v[0]點
7 for(int i=1;i<=n;i++)
8 {
9 //查找最近點
10 int minn=INF,k=0;
11 for(int j=0;j<=n;j++)
12 if(!vis[w]&&dis[j]<minn)
13 minn=dis[w],k=j;
14 vis[k] = 1;//标記查找到的最近點
15 //判斷是直接v[0]連接配接v[j]短，還是經過v[k]連接配接v[j]更短
16 for(int j = 1; j <= n; j++)
17 if(!vis[j]&&minn+w[k][j]<dis[j])
18 d[j]=minn+w[k][j];
19 }
20 return dis[j];
21 } 複制
貼上一道Dijkstra裸題：HDU 2544
下面是DijkstraAC的代碼：
1 #include<stdio.h>
2 #include<string.h>
3 #define inf 0xfffffff
4 int mp[110][110],dis[110],visit[110];
5 int n,m;
6 int Dijstra()
7 {
8 int i,j,pos=1,minn,sum=0;
9 memset(visit,0,sizeof(visit));
10 for(i=1;i<=n;++i)
11 {
12 dis[i]=mp[1][i];
13 }
14 visit[1]=1;
15 dis[1]=0;
16 for(i=1;i<n;i++)
17 {
18 minn=inf;
19 for(j=1;j<=n;++j)
20 {
21 if(!visit[j]&&minn>dis[j])
22 {
23 minn=dis[j];
24 pos=j;
25 }
26 }
27 sum+=minn;
28 visit[pos]=1;
29 for(j=1;j<=n;++j)
30 {
31 if(!visit[j]&&dis[j]>dis[pos]+mp[pos][j])
32 dis[j]=dis[pos]+mp[pos][j];
33 }
34 }
35 return dis[n];
36 }
37 int main()
38 {
39 int i,j;
40 while(~scanf("%d%d",&n,&m),n||m)
41 {
42 for(i=1;i<=n;++i)
43 {
44 for(j=1;j<=n;++j)
45 {
46 mp[i][j]=inf;
47 }
48 }
49 int a,b,c;
50 for(i=1;i<=m;++i)
51 {
52 scanf("%d%d%d",&a,&b,&c);
53 if(c<mp[a][b])
54 mp[a][b]=mp[b][a]=c;
55 }
56 int count=Dijstra();
57 printf("%d\n",count);
58 }
59 return 0;
60 } 複制
當時我是用Floyd過的，有興趣的點選這裡
下面是一些題目的錦集，有興趣的同學可以做做看哦
1.poj1062 昂貴的聘禮（中等）
此題是個經典題目；用Dijkstra即可；但是其中的等級處理需要一定的技巧；
要了解好那個等級制度；這個處理好，基本就是裸體Dijkstra；
2 poj1125 Stockbroker Grapevine（基本）
這個是簡單Floyd，需要求出的是每對頂點之間的最短路徑；
然後找到那個所需時間最小的那個人中的所需時間；
3，poj 1502 MPI Maelstrom（基本）【已經解決之，Dijkstra直接水之】
這題是鄰接矩陣的Dijkstra就可以解決的；
直接水之；
4，poj 1511 Invitation Cards（中等）
這個時間上有點卡了。Dijkstra，bellman可能會TLE；用SPFA+鄰接表可以過的；
有個地方注意一下就好了，每個志願者回來的時候的最短路徑；将原圖的每條邊反向一下，對端點1再來
SPFA就可以來；
正向圖的結果+逆向圖的結果就是所求；
5，poj 1724 ROADS（中等偏上）
題意是在一定的coins的限制下的最短路徑；可以用Dijkstra的變形；
用鄰接邊來存儲邊；
松弛過程中用優先隊列（邊的長度短的優先）來存儲邊，将符合條件（coins限制）的邊都加入優先隊列；
直到找到延伸到最後一個頂點即可終止循環； 因為最先到達的一定是最短路徑，在coins的限制條件下；
6，poj1797 Heavy Transportation（中等）
從端點1到端點n的能夠通過的最大載重；
可以用Dijkstra變形一下，在松弛時要改變一下松弛的條件；
另外results數組中存儲的不是每個點到1的最短距離，而是能夠通過的最大載重；
這題的輸出讓我灰常無語，以後輸出要看清啦。。
7，poj 1860 currency exchange（基本）
這個是bellman_ford的經典應用；
一個套彙問題，就是通過一系列的貨币交換能夠到達價值增加的目的；
就是類似判斷有沒有負權回路；
類似與poj2240，poj3259；
8，poj2240 Arbitrage（基本）http://hi.baidu.com/lewutian
這個是poj1860的簡化版本；就不多說了。。
直接bellman水之；
9，poj 2253 Frogger（中等）
和poj1797類似，所求的正好相反，也是Dijkstra的變形經典應用；
改變一下松弛時的條件；
10，poj 2387 Till the Cows come home（基本）
注意其中可能有重邊；然後就是赤裸的Dijkstra；
11，poj 2502 Subway（基本）
可以用Floyd來搞定，關鍵是哪個邊的存儲，存儲後就是灰常簡單的Floyd了；
12，poj 3013 Big Christmas Tree（中等）
這個要有個重要的轉化；首先price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).
這句指出每條邊的代價為該邊所有子孫節點權值之和乘以該邊的權值。
換個角度就是每個節點的代價為該節點到根節點的所有邊的權值乘以該節點的權值。
其實就是求從端點1到每個點的最短路徑*改點的權值，，然後之和；
貌似，資料有點大，用SPFA吧。。
13，poj 3037 Skiing（中等）
這個題有點意思；剛開始想用bfs；
後來發現對于每個點從該點出發的速度是恒定的，例如從a->b->c;則c出發的速度就是V*2^(A-B）*2^(B-C)=V*2^(A-C);
是以直接求最短路徑就可以了，邊也知道了。用spfa。。
14，poj 3159 Candies（中等）
我靠，這個題時間卡的好緊啊！我的spfa是1400ms，時限是1500ms，汗一下；
題意有點難了解，想明白了，其實就是求一個從1->n的最短路徑；
15，poj 3259 Wormholes（簡單）
這個題和poj1860，poj3259基本一樣；
求負權回路是否存在；用bellman直接水之；
16，poj 3268 Silver Cow Party（基本）
Dijkstra可以直接過的。。隻不過求的有變化；
17，poj 3377Ferry Lanes（中等）
這題可以用最短路做的；但是我看和導論那個流水線那個dp例子灰常像；
于是就dp過了，其中有個地方需要注意，dp的話，就是可以需要檢查兩端的情況；
有興趣的可以兩種都試試；
18，poj 3615 Cow Hurdles（中等）
Floyd求出每個端點之間的路徑中最大高度是最小的那個最大高度；
要改變一下松弛的條件；
19，poj 3660 Cow Contest（中等）
這個題有點topsort的意思，其實可以用Floyd來做，而且用的很巧妙；
鄰接矩陣中用0，1，2來分别存儲關系不能确定，在之前，在之後；
然後判斷每個點哪行，如果除了對角線處，沒有0出現的話，那麼它的位置就可以确定了。。
Dijkstra所需的資料結構：
dist[]數組，用于存儲每個點的字首點，可以從終點回溯整個最短路徑；
shortest[]數組，用于存儲目前該點的最短距離；
ifVisited[]數組，用于将已經找到最短路徑的點篩選出去。
回顧一下dijkstra的幾個基本步驟：
1.初始化起點，初始化所有數組，起點的shortet設定為0；
2.開始周遊所有點V次，V為頂點數目-1；
3.每次周遊的開始，選出shortest的頂點，将ifVisited置為true；
4.周遊過程中，如果目前篩選出的點的dist+兩點間距離<某個點的shorest,則更新該點的shortest；
最終，shortest記錄的是原點到每個點的最短距離。
局限性：Dijkstra不能求出任意兩個點之間的最短路徑，隻能求出某一點到其他任一點的最短路徑，并且不支援負權邊；
如果要支援負權邊，則使用bellman-ford，如果要支援任意兩點最短路徑，需要使用flyod。
要技藝超群，要予人溫暖，越努力才能越幸運，不讓那些為我付出過的人失望 -----Angel_Kitty