单源最短路径
对于图G =(V,E),给定源点 s 属于 V ,单源路径是指从 s 到图中其他各顶点的最短路径.
下图为带权有向图,从 v0 到其余各个顶点的最短路径如表所示。
源点 | 终点 | 最短路径 | 路径长度 |
---|---|---|---|
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算法
设图的邻接矩阵为 W ,Dijkstra 算法首先将图的顶点集合划分成两个集合 S 和 V-S 。
集合 S 表示最短路径已经确定的顶点集合,其余的顶点则存放在另一个集合 V-S 中。
初始状态时,集合 S 至包括源点,即 S = {s} ,表示此时只有源点到自己的最短路径称为从源点到顶点 v 到最短路径,并用数组 D 来记录当前所找到的从源点 s 到每个顶点的最短路径长度,用数组 path 来记录到达各个顶点的前驱顶点。
其中,如果从源点 s 到顶点 c 有弧 ,则以弧到权值作为 D[v] 的初始值;否则将 D[v] 的初始为无穷大,path 数组初始化为 s 。
Dijkstra 算法每次从尚未确定最短路径长度的集合 V-S 中取出一个最短特殊路径长度最小的顶点 u ,将 u 加入集合 S ,同时更新数组 D 、path 中由 s 可达大各个顶点的最短特殊路径长度。
更新 D 的策略是,若加进 u 做中间顶点,使得 vi 的最短特殊路径长度变短,则修改 vi 的最短特殊路径长度及前驱顶点编号,即当 D[u]+W[u ,vi]<D[vi] 时,令 D[vi] = D[u]+W[u,vi], path[vi] = u 。重复上述操作,一旦 S 包含了 V 中所有的顶点, D 记录了从源点 s 到各个顶点的最短路径长度,path 记录了相应最短路径的终点的前驱顶点编号。
下表直观地表示了 v0 到图中其他顶点的最短路径及最短路径长度。
顶 点 | {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 | |
新顶点 | v2 | v1 | v4 | v3 | v5 | |
路径长度 | 10 | 12 | 30 | 50 | 60 |
代码实现
1.定义一个结构体,用来记录每个顶点的最短路径。
struct Path{
string route;
Path(){
route = "";
}
};
2.Dijkstra 算法的实现
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;
}
}
}