摘要

最短路徑問(wèn)題是一個(gè)在圖論研究中很經(jīng)典的問(wèn)題，已經(jīng)被應(yīng)用到GIS床未、GPS等信息管理系統(tǒng)中镀层，為人們生活帶來(lái)了很大的便利。由于在現(xiàn)實(shí)生活中羡亩，我們所遇到的路徑問(wèn)題大都不含負(fù)權(quán)，所以Dijkstra算法在解決有關(guān)最短路徑問(wèn)題時(shí)算是最普遍的算法之一危融。如果在一個(gè)圖論研究中已知起點(diǎn)和終點(diǎn)求最短路徑畏铆，很適合使用Dijkstra算法，以下內(nèi)容我將闡述Dijkstra算法吉殃。

介紹

1.基本思想：從圖的給定源點(diǎn)到其他各個(gè)頂點(diǎn)之間客觀上應(yīng)存在一條最短路徑辞居，在這組最短路徑中，按其長(zhǎng)度的遞增次序蛋勺，依次求出到不同頂點(diǎn)的最短路徑和路徑長(zhǎng)度速侈。即按長(zhǎng)度遞增的次序生成各頂點(diǎn)的最短路徑，即先求出長(zhǎng)度最小的一條最短路徑迫卢，然后求出長(zhǎng)度第二小的最短路徑，以此類推冶共，直接求出長(zhǎng)度最長(zhǎng)的最短路徑乾蛤，核心是通過(guò)遞歸的方式將從起始頂點(diǎn)到其他各頂點(diǎn)的最短路徑全部求出每界。

2.為什么不能處理負(fù)權(quán)邊的問(wèn)題

舉個(gè)例子，如果要尋找B到C之間的最短路徑家卖。使用Dijkstra算法時(shí)眨层，比較從B->A和B->C的開(kāi)銷，顯然B->A的更小上荡，于是選擇C的路徑趴樱，并將C處理成處理過(guò)的節(jié)點(diǎn)，但是明明B到A到C更短酪捡。(如圖1.2）

圖片發(fā)自簡(jiǎn)書App

3.符號(hào)表示：V:所有結(jié)點(diǎn)的集合叁征。

S:結(jié)點(diǎn)集合，確定最短路徑結(jié)點(diǎn)的集合逛薇。

Q:最小優(yōu)先隊(duì)列捺疼。

s:源結(jié)點(diǎn)。

u:選擇最短路徑估計(jì)最小的結(jié)點(diǎn)永罚。

4.算法思想說(shuō)明：

設(shè)給定源點(diǎn)為Vs啤呼，S為已求得最短路徑的終點(diǎn)集，開(kāi)始時(shí)令S={Vs} 呢袱。當(dāng)求得第一條最短路徑(Vs 官扣，Vi)后，S為{Vs羞福，Vi} 惕蹄。設(shè)下一條最短路徑終點(diǎn)為Vj ，則Vj只有：

（1）? 源點(diǎn)到終點(diǎn)有直接的弧<Vs坯临，Vj>焊唬；

（2）從Vs 出發(fā)到Vj 的這條最短路徑所經(jīng)過(guò)的所有中間頂點(diǎn)必定在S中。即只有這條最短路徑的最后一條弧才是從S內(nèi)某個(gè)頂點(diǎn)連接到S外的頂點(diǎn)Vj 看靠。?

若定義一個(gè)數(shù)組dist[n]赶促，其每個(gè)dist[i]分量保存從Vs 出發(fā)中間只經(jīng)過(guò)集合S中的頂點(diǎn)而到達(dá)Vi的所有路徑中長(zhǎng)度最小的路徑長(zhǎng)度值，則下一條最短路徑的終點(diǎn)Vj必定是不在S中且值最小的頂點(diǎn)挟炬，即： dist[i]=Min{ dist[k]| Vk∈V-S }

5.特點(diǎn)：

時(shí)間復(fù)雜度為0 (N^2);

單源點(diǎn)最短路鸥滨；

較穩(wěn)定；

（4）代碼較簡(jiǎn)單;

（5）負(fù)權(quán)回路不適用;

（6）可用堆優(yōu)化谤祖。

二.分析

Dijkstra算法主要執(zhí)行是：

數(shù)組變量的初始化：時(shí)間復(fù)雜度是O(n) 婿滓；

求最短路徑的二重循環(huán)：時(shí)間復(fù)雜度是O(n2) ；

算法實(shí)現(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 ;?

? ? ? ? ? }

? ? }? ?

}? ?

}

算法過(guò)程示意圖（圖2.3）

圖片發(fā)自簡(jiǎn)書App

1.初始化數(shù)D = [0, inf, 10, inf, 30, 100],

T= {v1}

2.當(dāng)前離起始點(diǎn)v1最近的點(diǎn)是v3,那么可以確定v1和03的最近距離就是當(dāng)前D[2]的值,并將03加入T中粥喜。

3. 既然確定了一個(gè)頂點(diǎn)的最短路徑凸主，下面就要根據(jù)這個(gè)新入的頂點(diǎn)v3的出度，發(fā)現(xiàn)以03的出度的有: {04} ,那么查看路徑: 01- 03- v4的長(zhǎng)度是否比01- 04短,（因?yàn)镈[3]代表的就是v1- 04的長(zhǎng)度為無(wú)窮大额湘，而v1- V3- v4的長(zhǎng)度為: 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的出度是否會(huì)影響我們的數(shù)組D的值磺樱，05有 兩條出度:{04, v6}可以發(fā)現(xiàn): 01- 05- v4的長(zhǎng)度為: 50， 而01- v4的值為60婆咸，所以更新D[3]的值另外竹捉，01- 05 - v6的長(zhǎng)度為: 90,而01- 06為100，所以需要更新D[5]的值擅耽。更新結(jié)果如下:

D= [0, inf,10, 50,30,90],T= {01, 03,05}

5.繼續(xù)從D中選擇未確定的頂點(diǎn)的值中選擇一個(gè)最小的值活孩，發(fā)現(xiàn)D[3]的值是最小的，所以把v4加入到集合T中乖仇，考慮v4的出度憾儒，v4有一條出度: {v6} 然后可以發(fā)現(xiàn):01-05- 04- v6的長(zhǎng)度為: 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}。

三.實(shí)現(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");

}

? ?

圖片發(fā)自簡(jiǎn)書App

四．總結(jié)

最短路徑理論可以很好地應(yīng)用到生活中警儒，具有很重要的作用和意義训裆，Dijkstra算法適用于邊權(quán)為正的無(wú)向和有向圖不適用于有負(fù)邊權(quán)的圖，可以將實(shí)際生活中出現(xiàn)的問(wèn)題優(yōu)化得以解決蜀铲。目前边琉，最短路徑問(wèn)題大多出現(xiàn)在道路建設(shè)方面，利用一些算法來(lái)將一些虛擬的想象和數(shù)字變成一串真實(shí)有依據(jù)的代碼和數(shù)據(jù)记劝，這些計(jì)算算法真的起到了很重要的作用变姨。

參考文獻(xiàn)：

1.《數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）》，嚴(yán)蔚敏厌丑，吳偉民定欧，清華大學(xué)出版社，P189怒竿。

2.博客園-最短路徑問(wèn)題（Dijkstra算法的解釋）砍鸠。

3.簡(jiǎn)書社區(qū)—Dijkstra最短路徑算法。

4.簡(jiǎn)書社區(qū)—圖之最短路徑耕驰。

5.OSCHINA社區(qū)—圖的最短路徑爷辱。

6.慕課手記—圖經(jīng)典算法之-Dijkstra算法。

?