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

很明显的，迭代次数是有下限的，最短路径上要经过多少个顶点，至少就要迭代多少次，我们只能使得最终的迭代次数接近最少需要的次数。如果再要减低算法的时间复杂度，我们只能想办法把搜索范围的O(n)变为O(1)，这样，即使迭代了N－1次才得到结果，那时间复杂度仍为O(n)。但这个想法实现起来却是困难重重。

仍然看Dijkstra算法，第一步要寻找S中的顶点到S外面顶点中最短的一条路径，这个min运算使用基于比较的方法的时间复杂度下限是O(longN)（使用败者树），然后需要扫描结果数组的每个分量进行修改，这里的时间复杂度就只能是O(n)了。原始的Dijkstra算法达不到预期的目的。

现在让我们给图添加一个附加条件——两点之间直线最短，就是说如果v1和v2之间有直通的路径（不经过其他顶点），那么这条路径就是他们之间的最短路径。这样一来，如果求的是v1能够直接到达的顶点的最短路径，时间复杂度就是O(1)了，显然比原来最好的O(n)（这里实际上是O(logN)）提高了效率。

这个变化的产生，是因为我们添加了“两点之间直线最短”这样的附加条件，实际上就是引入一个判断准则，把原来盲目的O(n)搜索降到了O(1)。这个思想就是A*算法的思想。关于A*算法更深入的介绍，恕本人资料有限，不能满足大家了。有兴趣的可以到网上查查，这方面的中文资料实在太少了，大家做好看E文的准备吧。

不同于现有的教科书，我把求最短路径的算法的介绍顺序改成了上面的样子。我认为这个顺序才真正反映了问题的本质——当减低问题规模时，为了降低算法的时间复杂度，应该想办法缩小搜索范围。而缩小搜索范围，都用到了一个思想——尽可能的向接近最后结果的方向搜索，这就是贪婪算法的应用。

如果反向看一遍算法的演化，我们还能得出新的结论。Dijkstra算法实际上不用做n2次搜索、比较和修改，当求出最短路径的顶点后，搜索范围已经被缩小了，只是限于储存结构，这种范围的缩小并没有体现出来。如果我们使得这种范围缩小直接体现出来，那么，用n次Dijkstra算法代替Floyed算法就能带来效率上的提升。A*算法也是如此，如果用求n点的A*算法来代替Dijkstra算法，也能带来效率的提升。

但是，每一步的进化实际上都伴随着附加条件的引入。从Floyed到Dijkstra是边上的权值非负，如果这个条件不成立，那么就只能退化成Bellman-Ford算法。从Dijkstra到A*是另外的判断准则的引入（本文中是两点之间直线最短），如果这个条件不成立，同样的，只能采用不完整的Dijkstra（求到目的顶点结束算法）。

活动网络（AOV、AOE）

这部分是和工程相关的，也就是说，当AOV、AOE很复杂的时候，才能显示出这部分的价值——简单的话，手工都要比程序快，输入数据那段时间手工结果就出来了。我也没什么例子好举，总给我一种没底气的感觉，勉为其难的把程序写完就算完事吧。和前边的相比，这部分专业了一点，换而言之，不是每个人都感兴趣，不想看就跳过去吧。

准备工作

活动网络主要有两个算法，拓扑排序和求关键路径，后者以前者为基础。仿照上篇，另外构造一个“算法类”，需要算法时，将图绑定到算法上。

#include "Network.h"
#define iterator list<Link<name, dist>::edge>::iterator
#define begin(i) G->data.vertices[i].e->begin()
#define end(i) G->data.vertices[i].e->end()
struct CriAct
{
CriAct() {}
CriAct(int source, int dest) : s(source), d(dest) {}
int s

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