孟凡升,小孩喝什么奶粉好,七七网
图论中，用来求最短路的方法有很多，适用范围和时间复杂度也各不相同。
它们的使用限制和运行时间如下：
dijkstra: 不含负权。运行时间依赖于优先队列的实现，如 o((∣v∣+∣e∣)log∣v∣)o((∣v∣+∣e∣)log∣v∣) spfa: 无限制。运行时间o(k?∣e∣) (k?∣v∣)o(k?∣e∣) (k?∣v∣) bellman-ford：无限制。运行时间o(∣v∣?∣e∣)o(∣v∣?∣e∣) asp: 无圈。运行时间o(∣v∣+∣e∣)o(∣v∣+∣e∣) floyd-warshall: 无限制。运行时间o(∣v∣3)
其中 1~4 均为单源最短路径 (single source shortest paths) 算法； 5 为全源最短路径 (all pairs shortest paths) 算法。顺便说一句，为什么没有点对点的最短路径？如果我们只需要一个起点和一个终点，不是比计算一个起点任意终点更节省时间么？答案还真不是，目前还没有发现比算从源点到所有点更快的算法。
本文中，前四个算法的图都采用邻接表表示法，如下：
我要评论
struct edge
{
int from;
int to;
int weight;
edge(int f, int t, int w):from(f), to(t), weight(w) {}
};
int num_nodes;
int num_edges;
vector edges;
vector g[max_nodes]; // 每个节点出发的边编号
int p[max_nodes]; // 当前节点单源最短路中的上一条边
int d[max_nodes]; // 单源最短路径长
dijkstra 方法依据其优先队列的实现不同，可以写成几种时间复杂度不同的算法。它是图论－最短路中最经典、常见的算法。关于这个方法，网上有许多分析，但是我最喜欢的还是《算法概论》中的讲解。为了理解 dijkstra 方法，首先回顾一下无权最短路的算法。无权最短路算法基于 bfs，每次从源点向外扩展一层，并且给扩展到的顶点标明距离，这个距离就是最短路的长。我们完全可以仿照这个思路，把带权图最短路问题规约到无权图最短路问题——只要把长度大于 1 的边填充进一些「虚顶点」即可。如下图所示。
这个办法虽然可行，但是显然效率很低。不过，dijkstra 方法ec,eb,ed分别出发，经过一系列「虚节点」，依次到达d,b,c 。为了不在虚节点处浪费时间，出发之前，我们设定三个闹钟，时间分别为4,3,2提醒我们预计在这些时刻会有重要的事情发生（经过实际节点）。更一般地说，假设现在我们处理到了某个顶点u，和u相邻接的顶点为v1,v2,…,vn，它们和uu的距离为d1,d2,…,dn。我们为v1,v2,…,vn各设定一个闹钟。如果还没有设定闹钟，那么设定为d ；如果设定的时间比d晚，那么重新设定为d（此时我们沿着这条路比之前的某一条路会提前赶到）。每次闹钟响起，都说明可能经过了实际节点，我们都会更新这些信息，直到不存在任何闹钟。综上所述，也就是随着 bfs 的进行，我们一旦发现更近的路径，就立即更新路径长，直到处理完最后（最远）的一个顶点。由此可见，由于上述「虚顶点」并非我们关心的实际顶点，因此 dijkstra 方法的处理方式为：直接跳过了它们。
还需要解决的一个问题，就是闹钟的管理。闹钟一定是从早到晚按顺序响起的，然而我们设闹钟的顺序却不一定按照时间升序，因此需要一个优先队列来管理。dijkstra 方法实现的效率严重依赖于优先队列的实现。一个使用标准库容器适配器priority_queue的算法版本如下：
typedef pair heapnode;
void dijkstra(int s)
{
priority_queue< heapnode, vector, greater > q;
for (int i=0; i n = q.top();
q.pop();
int u = n.second;
if (n.first != d[u]) continue;
for (int i=0; i d[u] + e.weight) {
d[e.to] = d[u] + e.weight;
p[e.to] = g[u][i];
q.push(make_pair(d[e.to], e.to));
}
}
}
}
dijkstra 方法的本质是进行一系列如下的更新操作：
然而，如果边权含有负值，那么 dijkstra 方法将不再适用。原因解释如下。
假设最终的最短路径为：
不难看出，如果按照
因此，为了求出负权图的最短路径，我们需要保证一个合理的更新序列。但是，我们并不知道最终的最短路径！因此一个简单的想法就是：更新所有的边，每条边都更新∣v∣?1次。由于多余的更新操作总是无害的，因此算法（几乎）可以正确运行。等等，为什么是∣v∣?1次？这是由于，任何含有∣v∣个顶点的图两个点之间的最短路径最多含有∣v∣?1条边。这意味着最短路不会包含环。理由是，如果是负环，最短路不存在；如果是正环，去掉后变短；如果是零环，去掉后不变。
算法实现中唯一一个需要注意的问题就是负值圈(negative-cost cycle)。负值圈指的是，权值总和为负的圈。如果存在这种圈，我们可以在里面滞留任意长而不断减小最短路径长，因此这种情况下最短路径可能是不存在的，可能使程序陷入无限循环。好在，本文介绍的几种算法都可以判断负值圈是否存在。对于 bellman-ford 算法来说，判断负值圈存在的方法是：在
bellman-ford 算法的代码如下：
bool bellman_ford(int s)
{
for (int i=0; i d[edges[e].from] + edges[e].weight
&& d[edges[e].from] != __inf) {
d[edges[e].to] = d[edges[e].from] + edges[e].weight;
p[edges[e].to] = e;
changed = true;
}
}
if (!changed) return true;
if (i == num_nodes && changed) return false;
}
return false; // 程序应该永远不会执行到这里
}
注记：
如果某次循环没有更新操作发生，以后也不会有了。我们可以就此结束程序，避免无效的计算。
上述程序中第 11 行的判断：如果去掉这个判断，只要图中存在负值圈函数就会返回false。否则，仅在给定源点可以达到负值圈时才返回false。
看来，bellman-ford 算法多少有些浪费。这里介绍的 spfa 可以算作是 bellman-ford 的队列改进版。在 dijkstra 方法中，随着 bfs 的进行，最短路一点一点地「生长」。然而如果存在负权，我们的算法必须允许「绕回去」的情况发生。换句话说，我们需要在某些时候撤销已经形成的最短路。同时，我们还要改变 bellman-ford 算法盲目更新的特点，只更新有用的节点。spfa 中，一开始，我们把源点 s放入队列中，然后每次循环让一个顶点u出队，找出所有与u邻接的顶点v，更新最短路，并当v不在队列里时将它入队。循环直到队列为空（没有需要更新的顶点）。 可以显示出 spfa 和 bellman-ford 算法相比的一个重大改进的最经典的一个例子，就是图为一条链的情形。 容易看出，如果存在负值圈，这个算法将无限循环下去。因此需要一个机制来确保算法得以中止。由于最短路最长只含有∣v∣?1条边，因此如果任何一个顶点已经出队∣v∣+1次，算法停止运行。 spfa 的代码如下：
bool in_queue[max_nodes];
int cnt[max_nodes];
bool spfa(int s)
{
int u;
queue q;
memset(in_queue, 0, sizeof(in_queue));
memset(cnt, 0, sizeof(cnt));
for (int i=0; i d[u] + e.weight) {
d[e.to] = d[u] + e.weight;
p[e.to] = g[u][i];
if (!in_queue[e.to]) {
q.push(e.to);
in_queue[e.to] = true;
if (++cnt[e.to] > num_nodes)
return false;
}
}
}
}
return true;
}
我们已经给出 spfa 的运行时间为
如果图是无圈的（acyclic）（或称为有向无环图，dag），那么情况就变的容易了。我们可以构造一个拓扑升序序列，由拓扑排序的性质，无圈图的任意路径中，顶点都是沿着「拓扑升序序列」排列的，因此我们只需要按照这个序列执行更新操作即可。显然，这样可以在线性时间内解决问题。
实现上，拓扑排序和更新可以一趟完成。这种算法的代码如下：
int indegree[max_nodes];
void asp(int s)
{
queue q;
for (int i=0; i d[w] + edges[g[w][i]].weight && d[w] != __inf) {
d[edges[g[w][i]].to] = d[w] + edges[g[w][i]].weight;
p[edges[g[w][i]].to] = g[w][i];
}
if (--indegree[edges[g[w][i]].to] == 0)
q.push(edges[g[w][i]].to);
}
}
}
floyd-warshall
与前面四种不同，floyd-warshall 算法是所谓的「全源最短路径」，也就是任意两点间的最短路径。它并不是对单源最短路径
floyd-warshall 算法如下：
int dist[max_nodes][max_nodes]; // 记录路径长
int path[max_nodes][max_nodes]; // 记录实际路径
bool floyd_warshall()
{
for (int i=0; i dist[i][k] + dist[k][j]
&& dist[i][k] != __inf && dist[k][j] != __inf) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[i][k];
if (i == j && dist[i][j] < 0)
return false;
}
}
}
}
return true;
}
其中dist数组应初始化为邻接矩阵。需要提醒的是，dist[i][i]实际上表示「从顶点 i 绕一圈再回来的最短路径」，因此图存在负环当且仅当 dist[i][i]<0。初始化时，dist[i][i]可以初始化为0，也可以初始化为
显示实际路径实际上非常简单。利用前四个算法提供的int *p，还原实际路径的一个方法如下：
void printpath(int from, int to, bool firstcall = true)
{
if (from == to) {
printf("%d", from);
return;
}
if (p[to] == -1) return;
if (firstcall) printf("%d ->", from);
int v = edges[p[to]].from;
if (v == from) {
if (firstcall) printf(" %d", to);
return;
}
printpath(from, v, false);
printf(" %d ->", v+1);
if (firstcall) printf(" %d", to);
}
利用 floyd-warshall 算法提供的int **path，还原实际路径的一个方法如下：
void showpath(int from, int to)
{
int c = from;
printf("%d -> %d:(%2d) %d", from, to, dist[from][to], from);
while (c != to) {
printf(" -> %d", path[c][to]);
c = path[c][to];
}
printf("\n");
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
Blazor server side 自家的一些开源的, 实用型项目的进度之 CEF客户端
.NET IoC模式依赖反转(DIP)、控制反转(Ioc)、依赖注入(DI)
vue+.netcore可支持业务代码扩展的开发框架 VOL.Vue 2.0版本发布
网友评论