摘要
最短路徑問題是一個在圖論研究中很經(jīng)典的問題，已經(jīng)被應用到GIS、GPS等信息管理系統(tǒng)中，為人們生活帶來了很大的便利。由于在現(xiàn)實生活中，我們所遇到的路徑問題大都不含負權(quán)，所以Dijkstra算法在解決有關(guān)最短路徑問題時算是最普遍的算法之一。如果在一個圖論研究中已知起點和終點求最短路徑，很適合使用Dijkstra算法，以下內(nèi)容我將闡述Dijkstra算法。
介紹
1.基本思想：從圖的給定源點到其他各個頂點之間客觀上應存在一條最短路徑，在這組最短路徑中，按其長度的遞增次序，依次求出到不同頂點的最短路徑和路徑長度。即按長度遞增的次序生成各頂點的最短路徑，即先求出長度最小的一條最短路徑，然后求出長度第二小的最短路徑，以此類推，直接求出長度最長的最短路徑，核心是通過遞歸的方式將從起始頂點到其他各頂點的最短路徑全部求出。
2.為什么不能處理負權(quán)邊的問題
舉個例子，如果要尋找B到C之間的最短路徑。使用Dijkstra算法時，比較從B->A和B->C的開銷，顯然B->A的更小，于是選擇C的路徑，并將C處理成處理過的節(jié)點，但是明明B到A到C更短。(如圖1.2）
3.符號表示：V:所有結(jié)點的集合。
S:結(jié)點集合，確定最短路徑結(jié)點的集合。
Q:最小優(yōu)先隊列。
s:源結(jié)點。
u:選擇最短路徑估計最小的結(jié)點。
4.算法思想說明：
設給定源點為Vs，S為已求得最短路徑的終點集，開始時令S={Vs} 。當求得第一條最短路徑(Vs ，Vi)后，S為{Vs，Vi} 。設下一條最短路徑終點為Vj ，則Vj只有：
（1）? 源點到終點有直接的弧<Vs，Vj>；
（2）從Vs 出發(fā)到Vj 的這條最短路徑所經(jīng)過的所有中間頂點必定在S中。即只有這條最短路徑的最后一條弧才是從S內(nèi)某個頂點連接到S外的頂點Vj 。?
若定義一個數(shù)組dist[n]，其每個dist[i]分量保存從Vs 出發(fā)中間只經(jīng)過集合S中的頂點而到達Vi的所有路徑中長度最小的路徑長度值，則下一條最短路徑的終點Vj必定是不在S中且值最小的頂點，即： dist[i]=Min{ dist[k]| Vk∈V-S }
5.特點：
時間復雜度為0 (N^2);
單源點最短路；
較穩(wěn)定；
（4）代碼較簡單;
（5）負權(quán)回路不適用;
（6）可用堆優(yōu)化。
二.分析
Dijkstra算法主要執(zhí)行是：
數(shù)組變量的初始化：時間復雜度是O(n) ；
求最短路徑的二重循環(huán)：時間復雜度是O(n2) ；
算法實現(xiàn)的關(guān)鍵：
BOOLEAN? final[MAX_VEX] ;
int? pre[MAX_VEX] , dist[MAX_VEX] ;
void Dijkstra_path (AdjGraph *G, int v)
? ? ? ? {? int j, k, m, min ;
for ( j=0; j<G->vexnum; j++)
{? pre[j]=v ;? final[j]=FALSE ;
dist[j]=G->adj[v][j] ;
}? dist[v]=0 ; final[v]=TRUE ;? ? ?
for ( j=0; j<G->vexnum-1; j++)
{? m=0 ;
while (final[m])? m++;?
min=INFINITY ;
for ( k=0; k<G->vexnum; k++)
? ? {? if? (!final[k]&&dist[m]<min)
? ? ? ? ? ? {? min=dist[k] ;? m=k ; }
}? ?
final[m]=TRUE ;? ?
for ( j=0; j<G->vexnum; j++)
? ? { if (!final[j]&&(dist[m]+G->adj[m][j]<dist[j]))
? ? ? ? ? {? dist[j]=dist[m]+G->adj[m][j] ;
? ? ? ? ? ? ? pre[j]=m ;?
? ? ? ? ? }
? ? }? ?
}? ?
}
算法過程示意圖（圖2.3）
1.初始化數(shù)D = [0, inf, 10, inf, 30, 100],
T= {v1}
2.當前離起始點v1最近的點是v3,那么可以確定v1和03的最近距離就是當前D[2]的值,并將03加入T中。
3. 既然確定了一個頂點的最短路徑，下面就要根據(jù)這個新入的頂點v3的出度，發(fā)現(xiàn)以03的出度的有: {04} ,那么查看路徑: 01- 03- v4的長度是否比01- 04短,（因為D[3]代表的就是v1- 04的長度為無窮大，而v1- V3- v4的長度為: 10+50=60）,所以更新D[3]的值，得到如下結(jié)果:? D= [0,inf, 10,60, 30, 100],T= {v1,v3}
4.從除v1和03外的其他值中尋找最小值，發(fā)現(xiàn)D[4]的值最小，同原，可以知道v1到v5的最短距離就是D[4]的值，然后，把v5加入到集合T中，考慮v5的出度是否會影響我們的數(shù)組D的值，05有 兩條出度:{04, v6}可以發(fā)現(xiàn): 01- 05- v4的長度為: 50， 而01- v4的值為60，所以更新D[3]的值另外，01- 05 - v6的長度為: 90,而01- 06為100，所以需要更新D[5]的值。更新結(jié)果如下:
D= [0, inf,10, 50,30,90],T= {01, 03,05}
5.繼續(xù)從D中選擇未確定的頂點的值中選擇一個最小的值，發(fā)現(xiàn)D[3]的值是最小的，所以把v4加入到集合T中，考慮v4的出度，v4有一條出度: {v6} 然后可以發(fā)現(xiàn):01-05- 04- v6的長度為: 60， 而v1- v6的值為90，所以更新D[5]的值,結(jié)果如下:
D = [0, inf, 10, 50, 30, 60]，T= {v1, V3, V5, v4}
6同理確定了v6和v2的最短路徑,得到的最終結(jié)果如下:
D= [0, inf, 10, 50,30, 60],
T= {v1, V3, U5, 0U4, V6, U2}。
三.實現(xiàn)
主要代碼：
#include<stdio.h>
#define INFINITY 9999
#define MAX 10
void dijikstra(int G[MAX][MAX], int n, int startnode);
int main(){
? ? int G[MAX][MAX], i, j, n, u;
? ? printf("\nEnter the no. of vertices:: ");
? ? scanf("%d", &n);
? ? printf("\nEnter the adjacency matrix::\n");
? ? for(i=0;i < n;i++)
? ? ? ? for(j=0;j < n;j++)
? ? ? ? ? ? scanf("%d", &G[i][j]);
? ? printf("\nEnter the starting node:: ");
? ? scanf("%d", &u);
? ? dijikstra(G,n,u);
}
void dijikstra(int G[MAX][MAX], int n, int startnode)
{
? ? int cost[MAX][MAX], distance[MAX], pred[MAX];
? ? int visited[MAX], count, mindistance, nextnode, i,j;
? ? for(i=0;i < n;i++)
? ? ? ? for(j=0;j < n;j++)
? ? ? ? ? ? if(G[i][j]==0)
? ? ? ? ? ? ? ? cost[i][j]=INFINITY;
? ? ? ? ? ? else
? ? ? ? ? ? ? ? cost[i][j]=G[i][j];
? ? for(i=0;i< n;i++) {
? ? ? ? distance[i]=cost[startnode][i];
? ? ? ? pred[i]=startnode;
? ? ? ? visited[i]=0;
? ? }
? ? distance[startnode]=0;
? ? visited[startnode]=1;
? ? count=1;
? ? while(count < n-1) {
? mindistance=INFINITY;
? ? ? ? for(i=0;i < n;i++)
? ? ? ? ? ? if(distance[i] < mindistance&&!visited[i]) {
? ? ? ? ? ? ? ? mindistance=distance[i];
? ? ? ? ? ? ? ? nextnode=i;
? ? ? ? ? ? }
? ? ? ? visited[nextnode]=1;
? ? ? ? for(i=0;i < n;i++)
? ? ? ? ? ? if(!visited[i])
? ? ? ? ? ? ? ? if(mindistance+cost[nextnode][i] < distance[i]) {
? ? ? ? ? ? ? ? ? ? distance[i]=mindistance+cost[nextnode][i];
? ? ? ? ? ? ? ? ? ? pred[i]=nextnode;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? count++;
? ? }
? ? for(i=0;i < n;i++)
? ? ? ? if(i!=startnode) {
? ? ? ? ? ? printf("\nDistance of %d = %d", i, distance[i]);
? ? ? ? ? ? printf("\nPath = %d", i);
? ? ? ? ? ? j=i;
? ? ? ? ? ? do {
? ? ? ? ? ? ? ? j=pred[j];
? ? ? ? ? ? ? ? printf(" <-%d", j);
? ? ? ? ? ? }
? ? ? ? ? ? while(j!=startnode);
? ? ? ? }
? ? printf("\n");
}
? ?
四．總結(jié)
最短路徑理論可以很好地應用到生活中，具有很重要的作用和意義，Dijkstra算法適用于邊權(quán)為正的無向和有向圖不適用于有負邊權(quán)的圖，可以將實際生活中出現(xiàn)的問題優(yōu)化得以解決。目前，最短路徑問題大多出現(xiàn)在道路建設方面，利用一些算法來將一些虛擬的想象和數(shù)字變成一串真實有依據(jù)的代碼和數(shù)據(jù)，這些計算算法真的起到了很重要的作用。
參考文獻：
1.《數(shù)據(jù)結(jié)構(gòu)（c語言版）》，嚴蔚敏，吳偉民，清華大學出版社，P189。
2.博客園-最短路徑問題（Dijkstra算法的解釋）。
3.簡書社區(qū)—Dijkstra最短路徑算法。
4.簡書社區(qū)—圖之最短路徑。
5.OSCHINA社區(qū)—圖的最短路徑。
6.慕課手記—圖經(jīng)典算法之-Dijkstra算法。
?
