最短路徑問題
看了王道的視訊，感覺雲裡霧裡的，是以寫這個部落格來加深了解。（希望能在12點以前寫完）
（floyd算法連結在底部，也可以直接點選這個超連接配接）
一、總體思想
1.初始化三個輔助數組
s[],dist[],path[]
s[]:這個數組用來标記結點的通路與否，如果該結點被通路，則為1，如果該結點還沒有通路，則為0；
dist[]:這個數組用來記錄目前從v到各個頂點的最短路徑長度，算法的核心思想就是通過不斷修改這個表實作；
path[]:這個數組用來存放最短路徑；
2.周遊圖，修改上面的各項數組，每次隻找最短路徑，直到周遊結束
二、代碼實作
1 void dijkstra(Graph G, int v)
2 {
3 int s[G.vexnum];
4 int dist[G.vexnum];
5 int path[G.vexnum];
6 for(int i = 0; i < G.vexnum; i++)
7 {
8 s[i] = 0;
9 dist[i] = G.edge[v][i];
10 if(G.edge[v][i] == max || G.edge[v][i] == 0)
11 {
12 path[i] = -1;
13 }
14 else
15 {
16 path[i] = v;
17 }
18 s[v] = 1;
19 }
20
21 for(int i = 0; i < G.vexnum; i++)
22 {
23 int min = max;
24 int u;
25 for(int j = 0; j < G.vexnum; j++)
26 {
27 if(s[j] != 1 && dist[j] < min)
28 {
29 min = dist[j];
30 u = j;
31 }
32 }
33 s[u] = 1;
34 for(int j = 0; j < G.vexnum; j++)
35 {
36 if(s[j] != 1 && dist[j] > dist[u] + G.edge[u][j])
37 {
38 dist[j] = dist[u] + G.edge[u][j];
39 path[j] = u;
40 }
41 }
42 }
43 } 三、代碼解釋
先自己定義一個無窮大的值max
#define max inf dijkstra算法傳入的兩個參為
圖Graph G；
起點結點 int v；
首先我們需要三個輔助數組
1 int s[G.vexnum];//記錄結點時是否被通路過，通路過為1， 沒有通路過為0
2 int dist[G.vexnum];//記錄目前的從v結點開始到各個結點的最短路徑長度
3 int path[G.vexnum];//記錄最短路徑，存放的是該結點的上一個為最短路徑的前驅結點 初始化三個數組
1 for(int i = 0; i < G.vexnum; i++)
2 {
3 s[i] = 0;//目前每個結點均未被通路過，設為0
4 dist[i] = G.edge[v][i];//dist[]數組記錄每個從v結點開到其他i結點邊的長度（權值）
5 if(G.edge[v][i] == max || G.edge[v][i] == 0)
6 {
7 path[i] = -1;
8 }//如果v到i不存在路徑或者i就是v結點時，将path[i]設為-1，意為目前v結點不存在路徑到i
9 else
10 {
11 path[i] = v;
12 }//反之，若v到i存在路徑，則v就是i的前驅結點，将path[i] = v
13 s[v] = 1;//從周遊起點v開始，即已經通路過頂點s[v]=1
14 } 開始周遊數組并且每次修改輔助數組以記錄目前的情況，直至周遊結束
1 for(int i = 0; i < G.vexnum; i++)
2 {
3 int min = max;//聲明一個min = max用來每次記錄這次周遊找到的最短路徑的長度（權值）
4 int u;//聲明u來記錄這次曆找到的最短路徑的結點
5 for(int j = 0; j < G.vexnum; j++)//開始周遊 找目前的最短路徑
6 {
7 if(s[j] != 1 && dist[j] < min)
8 {
9 min = dist[j];
10 u = j;
11 }//找出v到結點j的最短路徑，并且記錄下最短路徑的結點u = j
12 }
13 s[u] = 1;//找到結點u，即已通路過u，s[u] = 1
14 for(int j = 0; j < G.vexnum; j++)//開始周遊 修改輔助數組的值
15 {
16 if(s[j] != 1 && dist[j] > dist[u] + G.edge[u][j])
17 {
18 dist[j] = dist[u] + G.edge[u][j]；
19 path[j] = u;
20 }//如果v→j的路徑比v →u→j長，那麼修改dist[j]的值為 dist[u] + G.edge[u][j]，并且修改j的前驅結點為path[j] = u
21 }
22 } 周遊結束後，數組dist[]就是存放了起點v開始到各個頂點的最短路徑長度
最短路徑包含的結點就在path數組中
例如我們得到如下的path[]數組
1 path[0] = -1;//0到自己無前驅結點
2 path[1] = 0;//1的前驅為結點0,0無前驅結點，即最短路徑為0 →1
3 path[2] = 1;//2的前驅結為點1,1的前驅結點0，0無前驅結點，即最短路徑為0 →1 →2
4 path[3] = 0;//3的前驅為結點0,0無前驅結點，即最短路徑為0 →3
5 path[4] = 2;//4的前驅結為點2,2的前驅結為點1,1的前驅結點0，0無前驅結點，即最短路徑為0 →1 →2 →4 dijkstra對于存在負權值的圖不适用，明天再更新Floyd算法叭