数据结构学习(C++)之图

单源最短路径（Dijkstra算法）

仿照上面的Floyed算法，很容易的，我们能得出下面的算法：

void ShortestPath(int v1)
{
//Bellman-Ford
for (int k = 2; k < N; k++)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (length[v1][j] + length[j][i] < length[v1][i])
{
length[v1][i] = length[v1][j] + length[j][i];
path[v1][i] = j;
}
}

这就是Bellman-Ford算法，可以看到，采用Floyed算法的思想，不能使算法的时间复杂度从O(n3)降到预期的O(n2)，只是空间复杂度从O(n2)降到了O(n)，但这也是应该的，因为只需要原来结果数组中的一行。因此，我并不觉得这个算法是解决“边上权值为任意值的单源最短路径问题”而专门提出来的，是Dijkstra算法的“推广”版本，他只是Floyed算法的退化版本。

显然，Floyed算法是经过N次N2条边迭代而产生最短路径的；如果我们想把时间复杂度从O(n3) 降到预期的O(n2)，就必须把N次迭代的N2条边变为N条边，也就是说每次参与迭代的只有一条边——问题是如何找到这条边。

先看看边的权值非负的情况。假设从顶点0出发，到各个顶点的距离是a1,a2……，那么，这其中的最短距离an必定是从0到n号顶点的最短距离。这是因为，如果an不是从0到n号顶点的最短距离，那么必然是中间经过了某个顶点；但现在边的权值非负，一个比现在这条边还长的边再加上另一条非负的边，是不可能比这条边短的。从这个原理出发，就能得出Dijkstra算法，注意，这个和Prim算法极其相似，不知道谁参考了谁；但这也是难免的事情，因为他们的原理是一样的。

void ShortestPath(const name& vex1, const name& vex2)//Dijkstra
{
int v1 = G->find(vex1); int v2 = G->find(vex2);
if (shortest[v1]) { print(v1, v2); return; }
bool* S = new bool[N]; int i, j, k;
for (i = 0; i < N; i++) S[i] = false; S[v1] = true;
for (i = 0; i < N - 1; i++)//Dijkstra Start, like Prim?
{
for (j = 0, k = v1; j < N; j++)
if (!S[j] && length[v1][j] < length[v1][k]) k = j;
S[k] = true;
for (j = 0; j < N; j++)
if (!S[j] && length[v1][k] + length[k][j] < length[v1][j])
{
length[v1][j] = length[v1][k] + length[k][j];
path[v1][j] = k;
}
}
shortest[v1] = true; print(v1, v2);
}

如果边的权值有负值，那么上面的原则不再适用，连带的，Dijkstra算法也就不再适用了。这时候，没办法，只有接受O(n3) Bellman-Ford算法了，虽然他可以降低为O(n*e)。不过，何必让边的权值为负值呢？还是那句话，合理的并不好用。

特定两个顶点之间的最短路径（A*算法）

其实这才是我们最关心的问题，我们只是想知道从甲地到乙地怎么走最近，并不想知道别的——甲地到丙地怎么走关我什么事？自然的，我们希望这个算法的时间复杂度为O(n)，但是，正像从Floyed算法到Dijkstra算法的变化一样，并不是很容易达到这个目标的。

让我们先来看看Dijkstra算法求特定两个顶点之间的最短路径的时间复杂度究竟是多少。显然，在上面的void ShortestPath(const name& vex1, const name& vex2)中，当S[v2]==true时，算法就可以中止了。假设两个顶点之间直接的路径是他们之间的路径最短的（不需要经过其他中间顶点），并且这个路径长度是源点到所有目的点的最短路径中最短的，那么第一次迭代的时候，就可以得到结果了。也就是说是O(n)。然而当两个顶点的最短路径需要经过其他顶点

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!