当前位置：文档之家 › 最短路径算法

最短路径算法

  • 格式：doc
  • 大小：636.00 KB
  • 文档页数：34

算法的思想 (2)算法的描述 (2)算法的举例 (2)A*算法 (2)原理简介 (2)详细内容 (2)A*算法误区 (17)A*算法总结(Summary of the A* Method) (17)F LOYD算法 (17)定义 (17)核心思路 (18)算法过程 (18)优缺点分析 (18)J OHNSON算法 (23)Johnson算法要求 (23)Johnson算法结构要求 (23)Johnson算法数据结构 (23)Johnson算法的内容 (23)Johnson算法源程序 (23)D IJKSTRA算法 (27)算法简介 (27)算法描述 (27)复杂度分析 (27)算法实现 (28)测试样例 (30)算法应用的实例 (34)算法的思想设图中有n个结点，设置一个集会u，存放已经求出最短路径的结点（初始时u中的元素是源点），v-u是尚未确定最短路径的顶点的集合。

每次从v-u集合中找这样一个结点best_j：best_j是u集合中结点的邻接点，到源点的距离最短（等于到父结点的距离加上父结点到源点的距离）。

然后把该best_j置入u集合中，直到u=v。

算法的描述最短路经计算分静态最短路计算和动态最短路计算。

静态路径最短路径算法是外界环境不变，计算最短路径。

主要有Dijkstra算法，A*算法。

动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算最短路。

典型的有D*算法。

算法的举例A*算法原理简介A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。

公式表示为：f(n)=g(n)+h(n),其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。

但能得到最优解。

如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

估价值与实际值越接近，估价函数取得就越好。

例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。

明显优于Dijstra算法的毫无无方向的向四周搜索。

conditions of heuristicOptimistic (must be less than or equal to the real cost)As close to the real cost as possible详细内容初始A*算法主要搜索过程：创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。

遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->While(OPEN!=NULL){从OPEN表中取估价值f最小的节点n;if(n节点==目标节点) break;else{if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值if( X的估价值小于OPEN表的估价值)更新OPEN表中的估价值; //取最小路径的估价值if(X in CLOSE) 比较两个X的估价值//注意是同一个节点的两个不同路径的估价值if( X的估价值小于CLOSE表的估价值)更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值if(X not in both)求X的估价值;并将X插入OPEN表中; //还没有排序}将n节点插入CLOSE表中;按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。

启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。

当然A*也是。

这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。

象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。

这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。

最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。

这样可以有效的防止“最佳节点”的丢失。

那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法。

只不过要加上一些约束条件罢了。

由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。

A*算法是一个可采纳的最好优先算法。

A*算法的估价函数可表示为：f'(n) = g'(n) + h'(n)这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值。

由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。

g(n)代替g'(n)，但g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别的重要）。

可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。

我们说应用这种估价函数的最好优先算法就是A*算法。

举一个例子，其实广度优先算法就是A*算法的特例。

其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。

当然它是一种最臭的A*算法。

再说一个问题，就是有关h(n)启发函数的信息性。

h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。

这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。

但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。

就应该适当的减小h(n)的信息，即减小约束条件。

但算法的准确性就差了，这里就有一个平衡的问题。

概述虽然掌握了A* 算法的人认为它容易，但是对于初学者来说，A* 算法还是很复杂的。

搜索区域(The Search Area)我们假设某人要从A 点移动到B 点，但是这两点之间被一堵墙隔开。

如图1 ，绿色是A ，红色是B ，中间蓝色是墙。

图 1你应该注意到了，我们把要搜寻的区域划分成了正方形的格子。

这是寻路的第一步，简化搜索区域，就像我们这里做的一样。

这个特殊的方法把我们的搜索区域简化为了2 维数组。

数组的每一项代表一个格子，它的状态就是可走(walkalbe) 和不可走(unwalkable) 。

通过计算出从A 到 B 需要走过哪些方格，就找到了路径。

一旦路径找到了，人物便从一个方格的中心移动到另一个方格的中心，直至到达目的地。

方格的中心点我们成为“节点(nodes) ”。

如果你读过其他关于A* 寻路算法的文章，你会发现人们常常都在讨论节点。

为什么不直接描述为方格呢？因为我们有可能把搜索区域划为为其他多变形而不是正方形，例如可以是六边形，矩形，甚至可以是任意多变形。

而节点可以放在任意多边形里面，可以放在多变形的中心，也可以放在多边形的边上。

我们使用这个系统，因为它最简单。

开始搜索(Starting the Search)一旦我们把搜寻区域简化为一组可以量化的节点后，就像上面做的一样，我们下一步要做的便是查找最短路径。

在A* 中，我们从起点开始，检查其相邻的方格，然后向四周扩展，直至找到目标。

我们这样开始我们的寻路旅途：1.从起点A 开始，并把它就加入到一个由方格组成的open list( 开放列表) 中。

这个open list 有点像是一个购物单。

当然现在open list 里只有一项，它就是起点A ，后面会慢慢加入更多的项。

Open list 里的格子是路径可能会是沿途经过的，也有可能不经过。

基本上open list 是一个待检查的方格列表。

2.查看与起点A 相邻的方格( 忽略其中墙壁所占领的方格，河流所占领的方格及其他非法地形占领的方格) ，把其中可走的(walkable) 或可到达的(reachable) 方格也加入到open list 中。

把起点A 设置为这些方格的父亲(parent node 或parent square) 。

当我们在追踪路径时，这些父节点的内容是很重要的。

稍后解释。

3. 把A 从open list 中移除，加入到close list( 封闭列表) 中，close list 中的每个方格都是现在不需要再关注的。

如下图所示，深绿色的方格为起点，它的外框是亮蓝色，表示该方格被加入到了close list 。

与它相邻的黑色方格是需要被检查的，他们的外框是亮绿色。

每个黑方格都有一个灰色的指针指向他们的父节点，这里是起点A 。

图 2下一步，我们需要从open list 中选一个与起点 A 相邻的方格，按下面描述的一样或多或少的重复前面的步骤。

但是到底选择哪个方格好呢？具有最小F 值的那个。

路径排序(Path Sorting)计算出组成路径的方格的关键是下面这个等式：F =G + H这里，G = 从起点A 移动到指定方格的移动代价，沿着到达该方格而生成的路径。

H = 从指定的方格移动到终点B 的估算成本。

这个通常被称为试探法，有点让人混淆。

为什么这么叫呢，因为这是个猜测。

直到我们找到了路径我们才会知道真正的距离，因为途中有各种各样的东西( 比如墙壁，水等) 。

我们的路径是这么产生的：反复遍历open list ，选择F 值最小的方格。

这个过程稍后详细描述。

我们还是先看看怎么去计算上面的等式。

如上所述，G 是从起点Ａ移动到指定方格的移动代价。

在本例中，横向和纵向的移动代价为10 ，对角线的移动代价为14 。

之所以使用这些数据，是因为实际的对角移动距离是2 的平方根，或者是近似的 1.414 倍的横向或纵向移动代价。

使是有10和14 就是为了简单起见。

比例是对的，我们避免了开放和小数的计算。

这并不是我们没有这个能力或是不喜欢数学。

合集下载

三种最短路径算法

三种最短路径算法

三种最短路径算法最短路径算法是图论中的一个重要问题，它的目标是在给定的图中找到两个顶点之间的最短路径。

在本文中，我们将介绍三种常见的最短路径算法：Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法。

一、Dijkstra算法Dijkstra算法是一种贪心算法，用于解决带权重的有向图或无向图中单源最短路径问题。

该算法由荷兰计算机科学家Edsger W. Dijkstra 于1956年提出。

1. 算法思想Dijkstra算法采用了一种逐步扩展的策略来找到从源节点到所有其他节点的最短路径。

具体来说，它从源节点开始，每次选择距离源节点最近的一个未标记节点，并将其标记为已访问。

然后，更新该节点的邻居节点到源节点的距离，并将它们加入到候选集合中。

重复这个过程直到所有节点都被标记为已访问。

2. 算法流程- 初始化：将源节点s到所有其他节点v的距离初始化为无穷大，将源节点s到自身的距离初始化为0。

- 选取当前距离源节点s最近且未被访问过的节点u。

- 标记节点u为已访问。

- 更新节点u的邻居节点v到源节点s的距离：如果从源节点s到u的距离加上从u到v的距离小于当前已知的从源节点s到v的距离，则更新从源节点s到v的距离。

- 重复步骤2-4，直到所有节点都被标记为已访问。

3. 算法实现Dijkstra算法可以用堆优化实现，时间复杂度为O(ElogV)，其中E是边数，V是顶点数。

该算法也可以用数组实现，时间复杂度为O(V^2)。

二、Bellman-Ford算法Bellman-Ford算法是一种解决带权重有向图或无向图中单源最短路径问题的动态规划算法。

该算法由美国计算机科学家Richard Bellman和Lester Ford于1958年提出。

1. 算法思想Bellman-Ford算法采用了一种松弛边的策略来找到从源节点到所有其他节点的最短路径。

具体来说，它先将所有节点到源节点的距离初始化为无穷大，将源节点到自身的距离初始化为0。

迪杰斯特拉最短路径算法

迪杰斯特拉最短路径算法

迪杰斯特拉最短路径算法迪杰斯特拉最短路径算法是一种求解从一点到其它所有点间的最短距离的经典算法。

这个算法的基本思想是通过一个当前最短距离的顶点集来求出从起点到其它所有顶点的最短路径。

迪杰斯特拉最短路径算法通常用于有权图中计算最短路径，即每条边都有一个权值。

算法思路迪杰斯特拉最短路径算法的核心思路在于维护一个记录起点到图中每个顶点的最短距离的数组dist[]，同时维护一个标记数组mark[]用于标记每个顶点是否已经被访问过。

首先将起点标记为已访问，并将其到其它所有顶点的距离初始化为无穷大。

然后遍历起点所有的邻居节点，更新其邻居节点到起点的距离，并将邻居节点标记为已访问，接着从未标记为访问过的节点中选取距离最小的节点作为下一个处理节点，直到所有的节点都被访问。

算法的详细流程如下：1.从起点s开始，将起点距离初始化为0，其它点的距离初始化为无穷大。

2.标记起点为已访问。

3.对起点s的所有邻居节点进行松弛操作：对于起点到邻居节点v的距离dist[v]，如果经过当前处理节点u的路径长度比原来的距离更短，则更新dist[v]和标记mark[v]。

4.从未标记为访问过的节点中选取距离最小的节点作为下一个处理节点。

5.对下一个处理节点进行松弛操作，以此类推，直到所有节点都被访问。

算法优化迪杰斯特拉最短路径算法存在一些优化算法，使得算法更加高效。

以下介绍几种优化算法：1.堆优化在每一次选取距离最小的未访问节点的过程中，可以使用堆优化算法将选取节点的时间复杂度从O(n)优化到O(logn)。

堆优化可以使用最小堆或者斐波那契堆。

2.早期退出如果当前处理的节点u到起点s的距离已经比dist[u]更大，那么就不需要继续处理u的邻居节点了。

这种情况下，可以提前结束算法，因为后面的处理节点不可能比u更优。

3.双向搜索通常来说，单向搜索是从起点向终点搜索，而双向搜索是从起点和终点同时搜索。

对于有向无环图，双向搜索可以大大降低时间复杂度，因为搜索过程中相遇的点一定是最短路径上的点。

c语言最短路径搜寻算法

c语言最短路径搜寻算法

c语言最短路径搜寻算法
C 语言最短路径搜寻算法常用于在网图中寻找两点之间的最短路径，其中网图的最短路径分为单源最短路径和多源最短路径。

以下是两种常见的最短路径搜寻算法：- Dijkstra 算法：从一个起始点出发，到达一个终点，通过对路径权值的累加，找到最短路径。

- Floyd 算法：对于网中的任意两个顶点来说，之间的最短路径不外乎有两种情况。

一种是直接从一个顶点到另一个顶点的边的权值；另一种是先经过若干个顶点，最终达到另一个顶点，期间经过的边的权值和。

这两种算法都可以用 C 语言实现，你可以根据具体需求选择合适的算法。

若你想了解更多关于最短路径搜寻算法的内容，可以继续向我提问。

最短路径算法dijkstra算法python

最短路径算法dijkstra算法python

最短路径算法dijkstra算法python Dijkstra算法是一种用于求解图中两点之间最短路径的经典算法。

该算法由荷兰计算机科学家Edsger Dijkstra于1956年提出，至今仍然被广泛运用于各个领域，例如路由算法、网络优化、地图导航等。

本文将以Python 语言为基础，详细介绍Dijkstra算法的原理和实现过程。

一、Dijkstra算法的原理Dijkstra算法的核心思想是利用贪心策略逐步构建最短路径树。

该算法首先将起始节点的距离设置为0，将其他节点的距离设置为无穷大。

然后在每一轮选择距离起始节点最近的节点，并更新其周围节点的距离。

通过不断选择距离最近的节点，并更新距离，直到找到终点节点或所有节点都被访问完毕，即可得到起始节点到终点节点的最短路径。

二、算法的实现步骤下面将详细介绍Dijkstra算法的实现步骤。

1. 创建一个空的顶点集合visited和距离集合distance，并初始化起始节点的距离为0，其他节点的距离为无穷大。

2. 选择起始节点，并将其加入visited集合。

3. 遍历起始节点的邻居节点，计算起始节点到每个邻居节点的距离，并更新distance集合。

4. 在distance集合中选择距离起始节点最短的节点，将其加入visited 集合。

5. 重复步骤3和步骤4，直到终点节点被加入visited集合或所有节点都被访问完毕。

6. 根据visited集合和distance集合，可以得到起始节点到终点节点的最短路径。

三、Dijkstra算法的Python实现下面将使用Python语言实现Dijkstra算法，并解决一个具体的例子。

首先，创建一个图的类，包含节点和边的信息，并定义一些基本的方法。

其中，节点信息包括标识符、邻居节点和距离，边的信息包括起始节点、终点节点和权重。

pythonclass Graph:def __init__(self):self.nodes = []self.edges = []def add_node(self, node):self.nodes.append(node)def add_edge(self, start, end, weight):edge = (start, end, weight)self.edges.append(edge)接下来，实现Dijkstra算法的主要函数，用于求解最短路径。