算法描述
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算法——单源最短路」
