最短路径问题

无权图单源最短路径

无权图单源最短路径 .png

维护2个数组：
dist[w]，表示v到w的权值之和(初始时，dist[s] = 0，其余都为-1，s源点)
parent[w]，表示v到w的路线中w的父节点。(按这个遍历上去，就可以得到v到w的最短路径的路线)

void Unweighted(Vertex S)
{
    queue.EnQueue(S);
    while(!queue.IsEmpty()) {
        V = queue.DeQueue();
        for (V 的每一个邻接点 W) {
            if (dist[W] == -1) {
                dist[W] = dist[V] + 1;
                parent[W] = V;
                queue.EnQueue(W);
            }
        }
    }
}

有权图单源最短路径

a.png

有权图单源最短路径和无权图最短路径不一样，不能单从节点数来看，比如上图中，V1到V6，节点最少的路线是V1->V4->V6。但这并不是权值最小的。

Dijkstra算法

维护2个数组：
dist[w]，表示 v 到 w 的权值之和(初始时，dist[s] = 0，其余都为∞，s源点)
path[w]，表示 v 到 w 的路线中w的父节点。(按这个遍历上去，就可以得到v到w的最短路径的路线)

void Dijkstra(Vertex s)
{
    while(true) {
        V = 未收录顶点中dist最小值者。
        if (没有这样的顶点)
            break;
        
        collected[V] = true;

        for (V 的每一个邻接点W) {
            if (collected[W] == false) {
                dist[w] = dist[v] + E<V, W>
                path[w] = V;
            }
        }
    }
}

Dijkstra算法过程.png

多源最短路径