单源最短路径

对于图G =（V，E），给定源点 s 属于 V ，单源路径是指从 s 到图中其他各顶点的最短路径.

下图为带权有向图，从 v0 到其余各个顶点的最短路径如表所示。

image

Dijkstra

源点	终点	最短路径	路径长度
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}
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;
        }
    }    
}