2、AB程序计算最短路径,并画出最短路线图。关键词最短路径算法,最短路径应用,蚁群算法,浙江旅行商12目录摘要I关键词I第一章绪论2第二章最短路径算法2一、Dijkstra算法21、适用条件和范围22、算法描述23、算法实现2二、A*算法21、适用条件和范围32、算法原理33、算法描述3三、Bellman-Ford算法31、适用条件和范围32、算法描述43、算法实现4四、Topological Sort(拓扑排序)算法41、适用条件和范围42、算法描述43、算法实现4五、SSSP On DAG算法41、适
6、题的思路与方法,为比赛提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题。第二章最短路径算法本课题旨在总结归纳最短路径的普遍算法,经收集资料发现最短路径算法主要有:Dijkstra算法、A*算法、Bellman-Ford算法、Topological Sort(拓扑排序)算法、SSSP On DAG算法、Floyd算法、Prim算法、Kruskal算法及Johnson算法。其中最常用的路径算法有:Dijkstra算法、A*算法、Bellman-Ford算法及Floyd算法。一、Dijkstra算法1、
7、适用条件和范围:(1)单源最短路径(从源点s到其它所有顶点v);(2)有向图和无向图(无向图可以看作,同属于边集E的有向图);(3)所有边权非负(任取都有)。2、算法描述:如果v1→v2→v3→v4是v1→v4的最短路径,则v1→v2→v3一定是v1→v3的最短路径。v2→v3→v4一定是v2→v4的最短路径。3、算法实现:(1)初始化:dis[v]=maxint;dis[s]=0;pre[s]=s;S={s};(2)For i:=1 to n①取V-S中的一顶点u使得dis[u]=min{dis[v
8、]
9、v∈V-S}②S=S+{u}③For V-S中每个顶点v do Relax(3)算法结束:dis[i]为s到i的最短距离;pre[i]为i的前驱节点。程序见参考文献[8]。二、A*算法1、适用条件和范围:12A*算法属于一种启发式搜索。它扩展结点的次序类似于广度优先搜索,但不同的是每生成一个子结点需要计算估价函数F,以估算起始结点到该结点的代价及它到达目标结点的代价的和;每当扩展结点时,总是在所有待扩展结点中选择具有最小F值的结点作为扩展对象,以便使