我们更新dist数组后结果如上。
Dist[2] = min(dist[2], dist[1]+(1->2的权值))
Dist[3] = min(dist[3], dist[1]+(1->3的权值))
我们从数组中找一个最小的数值。上图中的点2，那么dist[2]已经可以确定了。因为边最短，走其他的路绕回来肯定路更长。
通过点2的边，我们可以更新dist数组，如果边能使得dist数值变小
(2)能到达3和4.
Dist[4]=min(dist[4], dist[2] + (2->4的权值))
Dist[3]=min(dist[3], dist[2] + (2->3的权值))
我们发现原来的dist[3]=4被dist[2]+(2->3的边)=3覆盖
Dist[4]=inf被dist[2]+(2->4的边)=7覆盖。
然后我们在选一条最短边。
把点3加入集合。扩展的两条边更新dist数组。
继续找最小
Dist数组计算完成。
在数据集合中选最小的数我们用优先队列logn，每次都能确定一个点，总过n个点。总复杂度O(nlogn)
写法和大部分和周三的prim算法几乎一模一样的，也分O(n^2)的版本和O(nlogn)优化的版本。一般肯定写快的O(nlogn)的；
//比较挫的O(N^2)版本，可能比较好理解
int dist[maxn], vis[maxn];
int dijkstra(int s, int t) { //从s->t的最短路径，无法到达反回-1
for(int i = 0; i < n; i ++ ) {
dist[i] = inf, vis[i] = 0;
}
dist[s] = 0;
for(int k = 1; k <= n; k ++ ) { ///dist数组n个，每次确定一个值
vis[s] = 1;
for(int i = first[s]; ~i; i = edge[i].next) { ///更新dist数组
int to = edge[i].to, w = edge[i].w;
if(!vis[to] && dist[to] > dist[s] + w) {
dist[to] = dist[s] + w;
}
}
int mincost = inf;
for(int i = 0; i < n; i ++ ) { ///找最小
if(!vis[i] && dist[i] < mincost) {
mincost = dist[i];
s = i;
}
}
}
if(dist[t] == inf) {
return -1;
} else {
return dist[t];
}
}
//优先队列实现
struct Node {
int to, cost;
Node() {}
Node(int tt, int cc):to(tt), cost(cc) {}
friend bool operator < (const Node &a, const Node &b) {
return a.cost > b.cost;
}
};
int dist[maxn], vis[maxn];
int dijkstra(int s, int t) {
for(int i = 0; i < n; i ++ ) {
dist[i] = inf, vis[i] = 0;
}
priority_queue<Node>que;
que.push(Node(s, 0));
/**
丢进去一个to=s,cost=0的结构体
等价于下面三行，看不懂往下翻附录构造函数
struct Node tmp;
tmp.to = s, tmp.cost = 0;
que.push(tmp);
*/
while(!que.empty()) {
Node now = que.top();
que.pop();
if(!vis[now.to]) {
vis[now.to] = 1;
dist[now.to] = now.cost;
for(int i = first[now.to]; ~i; i = edge[i].next) {
int to = edge[i].to, w = edge[i].w;
if(!vis[to]) {
que.push(Node(to, now.cost + w));
}
}
}
}
if(dist[t] == inf) {
return -1;
} else {
return dist[t];
}
}
SPFA算法(Shortest Path Fast Algorithm的缩写)
Ps: SPFA也叫bellman ford的队列优化。但是bellman ford的复杂度比较高。SPFA的平均复杂度是O(n*log2n)，复杂度不稳定，在稠密图(边多的图)跑的比dijkstra慢，稀疏图(边少的图)跑的比Dijkstra快。在完全图达到最坏的平方级复杂度。我们学它是因为有些图的边的长度是负数。这时候dijkstra就GG了。
完全图: n个点中如果每个点都与其他n-1有边，无向图中，就有n*(n-1)/2条边。
我们要求一个dist[]数组表示起点，到其他点的最短路径。