無權(quán)圖單源最短路徑

無權(quán)圖單源最短路徑 .png

維護2個數(shù)組：
dist[w]，表示v到w的權(quán)值之和(初始時，dist[s] = 0，其余都為-1，s源點)
parent[w]，表示v到w的路線中w的父節(jié)點。(按這個遍歷上去，就可以得到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);
            }
        }
    }
}

有權(quán)圖單源最短路徑

a.png

有權(quán)圖單源最短路徑和無權(quán)圖最短路徑不一樣，不能單從節(jié)點數(shù)來看，比如上圖中，V1到V6，節(jié)點最少的路線是V1->V4->V6。但這并不是權(quán)值最小的。

Dijkstra算法

維護2個數(shù)組：
dist[w]，表示 v 到 w 的權(quán)值之和(初始時，dist[s] = 0，其余都為∞，s源點)
path[w]，表示 v 到 w 的路線中w的父節(jié)點。(按這個遍歷上去，就可以得到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

多源最短路徑