（单源最短路）Dijkstra算法

算法描述

Dijkstra算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径权重被赋为 0 （d[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把d[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于所有顶点的集合 V 中的任意顶点 v， 若 v 不为 s 和上述 m 之一， d[v] = ∞）。当算法结束时，d[v] 中存储的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。
边的拓展是Dijkstra 算法的基础操作：如果存在一条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展一条从 s 到 v 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小，我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直运行到所有的 d[v] 都代表从 s 到 v 的最短路径的长度值。此算法的组织令 d[u] 达到其最终值时，每条边（u, v）都只被拓展一次。
算法维护两个顶点集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的顶点 v ，而集合 Q 则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对 u 的每条外接边 (u, v) 进行拓展。

伪代码

<pre>
对于节点集合(startV, endV):
找到离源点距离最近的点u从它开始扩展;
对于节点u的出边集合(nextV1, nextVn):
// 「松弛」当前节点的每一条出边
从当前节点curV扩展一条边(curV, nextVi),
观察能否通过这条边使d[curV]减小，
即d[curV] = min(d[curV], cost[curV, nextVi]);
</pre>

实现代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXV = 101;
const int MAXE = 10001;
const int INF = 0x3f3f3f3f;

struct edge {
    int to, cost;
};
vector<vector<edge> > lj(MAXV);
int v, e;
int d[MAXV];
bool vis[MAXV];

edge tempEdge(int t, int c) {
    edge ret;
    ret.to = t;
    ret.cost = c;
    return ret;
}
void Dijkstra(int s) {
    fill(vis + 1, vis + v + 1, false);
    fill(d + 1, d + v + 1, INF);
    for (edge E : lj[s])
        d[E.to] = E.cost;
    d[s] = 0;
    vis[s] = true;

    for (int i = 1; i < v; ++i) {
        int minD = INF;
        int minV;
        for (int j = 1; j <= v; ++j) {
            if (!vis[j] && d[j] < minD) {
                minD = d[j];
                minV = j;
            }
        }
        vis[minV] = true;

        for (edge E : lj[minV]) 
            d[E.to] = min(d[E.to], d[minV] + E.cost);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(false);

    while (cin >> v >> e && v && e) {
        for (int i = 1; i <= v; ++i)
            lj[i].clear();
        for (int i = 1; i <= e; ++i) {
            int f, t, c;
            cin >> f >> t >> c;
            lj[f].push_back(tempEdge(t, c));
            lj[t].push_back(tempEdge(f, c));
        }
        Dijkstra(1);
        cout << d[v] << endl;
    }
    return 0;
}

参考资料

• 维基百科「戴克斯特拉算法」条目
  https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95#p-search
• 《啊哈！算法》（by 纪磊） 「Dijkstra算法——单源最短路」