單源最短路徑
對(duì)于圖G =（V钦铺，E）蹦骑，給定源點(diǎn) s 屬于 V 民效，單源路徑是指從 s 到圖中其他各頂點(diǎn)的最短路徑.
下圖為帶權(quán)有向圖禀酱，從 v0 到其余各個(gè)頂點(diǎn)的最短路徑如表所示炬守。
| 源點(diǎn) | 終點(diǎn) | 最短路徑 | 路徑長(zhǎng)度 |
|---|---|---|---|
| v0 | v1 | V0->v1 | 12 |
| v2 | v0->v2 | 10 | |
| v3 | v0->v4->v3 | 50 | |
| v4 | v0->v4 | 30 | |
| v5 | v0->v4->v3->v5 | 60 |
Dijkstra算法
設(shè)圖的鄰接矩陣為 W ,Dijkstra 算法首先將圖的頂點(diǎn)集合劃分成兩個(gè)集合 S 和 V-S 。
集合 S 表示最短路徑已經(jīng)確定的頂點(diǎn)集合剂跟，其余的頂點(diǎn)則存放在另一個(gè)集合 V-S 中减途。
初始狀態(tài)時(shí)，集合 S 至包括源點(diǎn)曹洽，即 S = {s} 鳍置，表示此時(shí)只有源點(diǎn)到自己的最短路徑稱為從源點(diǎn)到頂點(diǎn) v 到最短路徑，并用數(shù)組 D 來(lái)記錄當(dāng)前所找到的從源點(diǎn) s 到每個(gè)頂點(diǎn)的最短路徑長(zhǎng)度送淆，用數(shù)組 path 來(lái)記錄到達(dá)各個(gè)頂點(diǎn)的前驅(qū)頂點(diǎn)税产。
其中，如果從源點(diǎn) s 到頂點(diǎn) c 有弧 ，則以弧到權(quán)值作為 D[v] 的初始值辟拷；否則將 D[v] 的初始為無(wú)窮大撞羽，path 數(shù)組初始化為 s 。
Dijkstra 算法每次從尚未確定最短路徑長(zhǎng)度的集合 V-S 中取出一個(gè)最短特殊路徑長(zhǎng)度最小的頂點(diǎn) u 衫冻，將 u 加入集合 S 诀紊，同時(shí)更新數(shù)組 D 、path 中由 s 可達(dá)大各個(gè)頂點(diǎn)的最短特殊路徑長(zhǎng)度隅俘。
更新 D 的策略是邻奠，若加進(jìn) u 做中間頂點(diǎn)，使得 vi 的最短特殊路徑長(zhǎng)度變短考赛，則修改 vi 的最短特殊路徑長(zhǎng)度及前驅(qū)頂點(diǎn)編號(hào)惕澎，即當(dāng) D[u]+W[u ,vi]<D[vi] 時(shí)，令 D[vi] = D[u]+W[u,vi], path[vi] = u 颜骤。重復(fù)上述操作唧喉，一旦 S 包含了 V 中所有的頂點(diǎn)， D 記錄了從源點(diǎn) s 到各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度忍抽，path 記錄了相應(yīng)最短路徑的終點(diǎn)的前驅(qū)頂點(diǎn)編號(hào)八孝。
下表直觀地表示了 v0 到圖中其他頂點(diǎn)的最短路徑及最短路徑長(zhǎng)度汁咏。
| 頂?點(diǎn) | ? | {v2} | {v2,v1} | {v2,v1,v4} | {v2,v1,v4,v3} | {v2,v1,v4,v3,v5} |
|---|---|---|---|---|---|---|
| v1 | 12 | 12 | ||||
| v2 | 10 | |||||
| v3 | ∞ | 60 | 60 | 50 | ||
| v4 | 30 | 30 | 30 | |||
| v5 | 100 | 100 | 100 | 90 | 60 | |
| 最短路徑 | v0v2 | v0v1 | v0v4 | v0v4v3 | v0v4v3v5 | |
| 新頂點(diǎn) | v2 | v1 | v4 | v3 | v5 | |
| 路徑長(zhǎng)度 | 10 | 12 | 30 | 50 | 60 |
代碼實(shí)現(xiàn)
1.定義一個(gè)結(jié)構(gòu)體月培，用來(lái)記錄每個(gè)頂點(diǎn)的最短路徑淹冰。
struct Path{
string route;
Path(){
route = "";
}
};
2.Dijkstra 算法的實(shí)現(xiàn)
void Dijkstra(int s,int D[]){
int n = VerticesNum();
path = new Path[n];
int i,j;
for(i = 0;i<n;i++){
D[i] = matrix[s][i];
path[i].route = "v"+to_string(s) + "-->" + "v" + to_string(i);
}
Mark[s] = VISITED;
D[s] = 0;
for(i = 0;i<n;i++){
//找到一條最短的特殊路徑
int min = INFINITY;
int k = 0;
for(j = 0;j<n;j++){
if(Mark[j]==UNVISITED&&min>D[j]){
min = D[j];
k = j;
}
}
Mark[k] = VISITED;
for(Edge e = FirstEdge(k);IsEdge(e);e = NextEdge(e)){
int endVertex = e.end;
if(Mark[endVertex]==UNVISITED&&D[endVertex]>(D[k] + e.weight)&&e.weight!=INFINITY){
//更新endVertex的最短特殊路徑
D[endVertex] = D[k] + e.weight;
path[endVertex].route = path[k].route + "-->v"+to_string(endVertex);
}
}
}
for(int i = 0;i<n;i++){
if(D[i]!=INFINITY){
cout<<path[i].route<<endl;
}
else{
cout<<"no road"<<endl;
}
}
}
