Dijkstra算法
定義概覽
Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。注意該算法要求圖中不存在負(fù)權(quán)邊。
問題描述：在無向圖 G=(V,E) 中，假設(shè)每條邊 E[i] 的長度為 w[i]，找到由頂點(diǎn) V0 到其余各點(diǎn)的最短路徑。（單源最短路徑）算法描述
- 算法思想：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長度。此外，每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長度，U中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。
- 算法步驟：
a.初始時(shí)，S只包含源點(diǎn)，即S＝{v}，v的距離為0。U包含除v外的其他頂點(diǎn)，即:U={其余頂點(diǎn)}，若v與U中頂點(diǎn)u有邊，則<u,v>正常有權(quán)值，若u不是v的出邊鄰接點(diǎn)，則<u,v>權(quán)值為∞。
b.從U中選取一個(gè)距離v最小的頂點(diǎn)k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。
c.以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u的距離（經(jīng)過頂點(diǎn)k）比原來距離（不經(jīng)過頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。
d.重復(fù)步驟b和c直到所有頂點(diǎn)都包含在S中。
/*** 遞歸
**graph：存儲圖信息的內(nèi)存地址，圖已排好序
**dist：圖中每個(gè)點(diǎn)到S點(diǎn)的距離，初始都為0
**v[]：圖中每個(gè)點(diǎn)是否訪問過的標(biāo)志
**vn:當(dāng)前訪問的節(jié)點(diǎn)ID
**uNum：圖中剩余沒訪問點(diǎn)數(shù)，為0則程序結(jié)束。
***/
void dijkstra(graph_t *graph, int dist[], int v[], int vn, int uNum)
{
if(uNum <= 0){
return;
}
printf("%d--%d\n",vn, uNum);
int flag = 1, vt = 0;
gnode_t *p = graph->relation[vn].next; /* 與VN相連接的點(diǎn) */
if(p == NULL){
return ;
}
v[vn] = 1;
while(p != NULL){ /* 訪問所有與VN相連接的點(diǎn) */
if(flag && !v[p->data]){ /* 與vn相連的未被訪問過的最近(越靠前越近)的點(diǎn)，用作往下遞歸的起點(diǎn) */
vt = p->data;
flag = 0;
}
if(0 == dist[p->data] || dist[p->data] > dist[vn] + p->weight){ /* 無向圖，p->weight為權(quán)重 */
dist[p->data] = dist[vn] + p->weight;
}
printf(" %d -- %d\n",p->data, dist[p->data]);
p = p->next;
}
dijkstra(graph, dist, v, vt, --uNum);
}
