本文乃Siliphen原创，转载请注明出处：http://blog.csdn.net/stevenkylelee
寻路算法实践一共2篇文章
下一篇《寻路算法实践2》：http://blog.csdn.net/stevenkylelee/article/details/7605836
最近一段时间学了 Qt , Boost , 图论基础算法 后，就做了这个练习作品。
本程序是为了测试，从点S到点D是否有通路。如果有通路，那么路径都是什么
最短的路径又是什么。
先上运行时的效果图吧。
（可执行程序和源代码下载在本帖末尾）
点击左下角的“开始搜索”按键后，就会按照按钮右边的组合框中选择的算法来搜索从S到D的路径。
目前实现的算法有：DFS，BFS，自己的一个启发式，Bellman-Ford , Dijkstra
如下图：
下图是用 Dfs 搜索的结果
在地图上右键，选择“显示搜索树”，会看到搜索过程生成的一棵“访问过的路径”的树映射到地图上的形态。
树节点的数值有2种。一种是顶点被的访问顺序号。另一种是顶点距离源点S的路径长度。
对于BFS，DFS来说，路径长度是顶点距离源点S的边数。
对于求最短路径算法来说，路径长度是距离源点S的边权值总和（定义直边是20，斜边28）
效果如下图：（嘿嘿，这可以方便直观地看到算法的执行效果）
DFS（随机） 是盲目搜索。
随机的意思是，在搜索过程中，随机选择当前访问的顶点的邻居顶点来入栈或入队。
所以，每次执行DFS、BFS（随机）生成的路径和路径树都可能不一样、
BFS（随机）有比较大的几率找到S到D的最短路径，但通常它只是找到一条接近最短路径的路径。
原因就是BFS只考虑边，而不考虑边的权值。（斜边的长度和直边是不同的）
我的启发式搜索，启发函数是优先挑选距离目的地D最近的那个顶点来扩展。
其实，我写的DFS，BFS，启发式 结构上都非常类似。OPEN表用STL的deque容器。
顶点的邻居顶点push_back到容器，然后容器从末端pop顶点出来扩展的话，就是DFS
从前端pop的话，就是BFS。
如果，根据某种信息从容器中挑选一个认为最有希望找到D的顶点出来扩展的话，就是启发式了。
当然，我的启发式很简单。能比较快地找到去D的路径，但不保证那条路径是最短的。- -
启发式效果图：
关于最短路径：
找最短路径有比较多的做法。本人水平有限，目前就只做了Bellman-Ford和Dijkstra。呵呵。
Bellman-Ford不复杂。一句话可以总结，那就是：对所有的边都进行N-1次松弛。
Bellman-Ford执行效果图：
Bellman-Ford 能计算负权回路，但执行效率比较低。
本程序中当然不存在负权值的边（一点到另一点的距离是负的，这不可能吧）
做上Bellman-Ford纯属练习咯。呵呵。
计算最短路径比Bellman-Ford快的，有Dijkstra。但Dijkstra只能计算没有负权回路的网。
Dijkstra也能用一句话总结：迭代N次，每次选择一个距离源点S最近的顶点出来，并松弛该顶点的所有邻边。
每次迭代选出一个顶点，就得到了源点S到该顶点的最短路径。
Dijkstra很类似BFS，它也是一圈圈地向外”扩张“找目的地。
Dijkstra执行效果如下：
最后，关于地图：
在地图上右键，弹出的菜单，可以编辑地图：重设起点、终点的位置。增加、删除障碍物。
地图也可以保存到文件，或从文件中载入。
本来，我打算用Boost的multi_array类，模拟动态二位数组，做地图的。
但该类与我用的Qt版本冲突，无法通过编译。
百度只出了一篇英文文章，说什么Qt语法扩展与该类实现代码不兼容。- -
没辙，只好自己封装个类，写operator=
内部维护一个 vector< vector< int > > 类型的对象做地图了。
我的程序的可执行文件下载地址：
http://download.csdn.net/detail/stevenkylelee/4054168
源代码下载地址：
http://download.csdn.net/detail/stevenkylelee/4054346
编写这个程序的环境是：
Qt Creator 2.8.1
Qt 4.7.4
Boost 1.48.0
除了C++语言外。做这程序的所有技术，俺都是最近学到的。
SO，肯定有巨多不足。这还望高手指点！
