Python小白的数学建模课-16.最短路径算法
发布网友
发布时间：2024-09-05 07:49
共1个回答
热心网友
时间：2024-10-01 16:28
最短路径问题有几种形式：确定起点的最短路径，确定终点的最短路径，确定起点和终点的最短路径，全局最短路径问题。
在日常生活中，最短路径长度与最短路径距离好像并没什么区别。但在图论中最短路径长度与最短路径距离却是不同的概念和问题，经常会被混淆。
图论中有无权图和有权图，无权图中的边没有权，赋权图的边带有权，可以表示距离、时间、费用或其它指标。在问题文字描述中，往往并不直接指出是无权图还是有权图，这时就要特别注意最短路径与最短加权路径的区别。
路径长度是把每个顶点到相邻顶点的长度记为 1，而不是指这两个顶点之间道路的距离——两个顶点之间的道路距离是连接边的权（weight）。
路径长度可以认为是飞行棋的步数，或者公交站点的站数，相邻顶点之间为一步，相隔几个顶点就是几站。路径长度是从路径起点到终点的步数，计算最短路径是要计算从起点到终点步数最少的路径。
如果问题不涉及相邻顶点间的距离，要计算从起点到终点的最短路径及对应的最短路径长度，是指这条路径从起点到终点有几步（站），在图论中称为最短路径长度。但是，如果问题给出相邻顶点之间的道路长度或距离，要计算从起点到终点的最短路径及对应的最短距离，显然并不是要找经过最少步数的路径，而是在找路径中各路段的距离之和最小的路径，在图论中称为最短加权路径长度——这里权重是路段距离。
相邻顶点的连接边的权，不仅可以是路段距离，也可以是时间、费用等指标。问题就变成寻求最短时间、最低成本的路径，这实际上也是最短加权路径长度问题。
求解最短路径长度的常用算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法，另外还有启发式算法 A*。
Dijkstra 算法是经典的最短路径算法，在数据结构、图论、运筹学中都是教学的基本算法。有趣的是，在数据结构中 Dijkstra 算法通常是按贪心法讲述，而在运筹学中则被认为是动态规划法。
Dijkstra算法从起点开始，采用贪心法策略，每次遍历距离起点最近且未访问过的邻接顶点， 层层扩展直到终点为止。
Dijkstra算法可以求出加权最短路径的最优解，算法的时间复杂度为O(n^2)。如果边数远小于 n^2，可以用堆结构将复杂度降为O((m+n)log(n))。
Dijkstar算法不能处理负权边，这是由于贪心法的选择规则决定的。
Bellman-Ford 算法是求含负权图的单源最短路径算法。算法原理是对图进行 V-1次松弛操作，得到所有可能的最短路径。
Bellman-Ford 算法可以处理负权边。其基本操作“拓展”是在深度上搜索，而“松弛”操作则在广度上搜索，因此可以对负权边进行操作而不影响结果。
Bellman-Ford 算法的效率很低，时间复杂度高达O(V*E)，V、E 分别是顶点和边的数量。SPFA 是 Bellman-Ford 的队列优化，通过维护一个队列极大地减少了重复计算，时间复杂度为 O(k*E) 。
Dijkstra 算法在求解过程中，起点到各顶点的最短路径求出后就不变了。Bellman算法在求解过程中，每次循环都要修改所有顶点间的距离，起点到各顶点最短路径一直要到算法结束才确定。
Floyd 算法又称插点法，运用动态规划思想求解有权图中多源点之间最短路径问题。算法从图的带权邻接矩阵开始，递归地进行 n 次更新得到图的距离矩阵，进而可以得到最短路径节点矩阵。
Floyd 算法的时间复杂度为O(n^3)，空间复杂度为 O(n^2)。算法时间复杂度较高，不适合计算大量数据。Floyd 算法的优点是可以一次性求解任意两个节点之间的最短距离，对于稠密图的效率高于执行 V 次 Dijkstra算法。
Floyd 算法可以处理负权边。
Floyd 算法号称只有 5行代码，我们来欣赏一下：
A*算法是一种静态路网中求解最短路径最有效的直接搜索方法。
A*算法是启发式算法，采用最佳优先（Best-first）搜索策略，基于估价函数对每个搜索位置的评估结果，猜测最好的位置优先进行搜索。
A*算法极大地减少了低质量的搜索路径，因而搜索效率很高，比传统的路径规划算法实时性更高、灵活性更强；但是，A*算法找到的是相对最优路径，不是绝对的最短路径，适合大规模、实时性高的问题。
NetworkX 提供了丰富的最短路径函数，除了常见的 Dijkstra 算法、Bellman-ford 算法、Floyd Warshall 算法和 A*算法，还有 Goldbery-Radzik 算法和 Johnson 算法。其中，Bellman-ford 算法函数使用的是队列改进算法，即以 SPFA 算法实现。
其中，最基本的求解最短路径函数 shortest() 和 最短路径长度 shortest_path_length() 是 ‘dijkstra’ 算法和 ‘bellman-ford’ 算法的集成接口，可以通过 method='dijkstra' 选择不同的算法。
shortest_path(G, source=None, target=None, weight=None, method='dijkstra') shortest_path_length(G, source=None, target=None, weight=None, method='dijkstra')
主要参数：
NetworkX 中关于 Dijkstra 算法提供了 13 个函数，很多函数的功能是重复的。这里只介绍最基本的函数 dijkstra_path() 和 dijkstra_path_length()。
dijkstra_path() 用于计算从源到目标的最短加权路径，dijkstra_path_length() 用于计算从源到目标的最短加权路径长度。
dijkstra_path(G, source, target, weight='weight') dijkstra_path_length(G, source, target, weight='weight')
主要参数：
NetworkX 中关于 Bellman-Ford 算法提供了多个函数，这里只介绍最基本的函数 bellman_ford_path() 和 bellman_ford_path_length()。
bellman_ford_path() 用于计算从源到目标的最短加权路径，bellman_ford_path_length() 用于计算从源到目标的最短加权路径长度。
bellman_ford_path(G, source, target, weight='weight') bellman_ford_path_length(G, source, target, weight='weight')
主要参数：
热心网友
时间：2024-10-01 16:36
最短路径问题有几种形式：确定起点的最短路径，确定终点的最短路径，确定起点和终点的最短路径，全局最短路径问题。
在日常生活中，最短路径长度与最短路径距离好像并没什么区别。但在图论中最短路径长度与最短路径距离却是不同的概念和问题，经常会被混淆。
图论中有无权图和有权图，无权图中的边没有权，赋权图的边带有权，可以表示距离、时间、费用或其它指标。在问题文字描述中，往往并不直接指出是无权图还是有权图，这时就要特别注意最短路径与最短加权路径的区别。
路径长度是把每个顶点到相邻顶点的长度记为 1，而不是指这两个顶点之间道路的距离——两个顶点之间的道路距离是连接边的权（weight）。
路径长度可以认为是飞行棋的步数，或者公交站点的站数，相邻顶点之间为一步，相隔几个顶点就是几站。路径长度是从路径起点到终点的步数，计算最短路径是要计算从起点到终点步数最少的路径。
如果问题不涉及相邻顶点间的距离，要计算从起点到终点的最短路径及对应的最短路径长度，是指这条路径从起点到终点有几步（站），在图论中称为最短路径长度。但是，如果问题给出相邻顶点之间的道路长度或距离，要计算从起点到终点的最短路径及对应的最短距离，显然并不是要找经过最少步数的路径，而是在找路径中各路段的距离之和最小的路径，在图论中称为最短加权路径长度——这里权重是路段距离。
相邻顶点的连接边的权，不仅可以是路段距离，也可以是时间、费用等指标。问题就变成寻求最短时间、最低成本的路径，这实际上也是最短加权路径长度问题。
求解最短路径长度的常用算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法，另外还有启发式算法 A*。
Dijkstra 算法是经典的最短路径算法，在数据结构、图论、运筹学中都是教学的基本算法。有趣的是，在数据结构中 Dijkstra 算法通常是按贪心法讲述，而在运筹学中则被认为是动态规划法。
Dijkstra算法从起点开始，采用贪心法策略，每次遍历距离起点最近且未访问过的邻接顶点， 层层扩展直到终点为止。
Dijkstra算法可以求出加权最短路径的最优解，算法的时间复杂度为O(n^2)。如果边数远小于 n^2，可以用堆结构将复杂度降为O((m+n)log(n))。
Dijkstar算法不能处理负权边，这是由于贪心法的选择规则决定的。
Bellman-Ford 算法是求含负权图的单源最短路径算法。算法原理是对图进行 V-1次松弛操作，得到所有可能的最短路径。
Bellman-Ford 算法可以处理负权边。其基本操作“拓展”是在深度上搜索，而“松弛”操作则在广度上搜索，因此可以对负权边进行操作而不影响结果。
Bellman-Ford 算法的效率很低，时间复杂度高达O(V*E)，V、E 分别是顶点和边的数量。SPFA 是 Bellman-Ford 的队列优化，通过维护一个队列极大地减少了重复计算，时间复杂度为 O(k*E) 。
Dijkstra 算法在求解过程中，起点到各顶点的最短路径求出后就不变了。Bellman算法在求解过程中，每次循环都要修改所有顶点间的距离，起点到各顶点最短路径一直要到算法结束才确定。
Floyd 算法又称插点法，运用动态规划思想求解有权图中多源点之间最短路径问题。算法从图的带权邻接矩阵开始，递归地进行 n 次更新得到图的距离矩阵，进而可以得到最短路径节点矩阵。
Floyd 算法的时间复杂度为O(n^3)，空间复杂度为 O(n^2)。算法时间复杂度较高，不适合计算大量数据。Floyd 算法的优点是可以一次性求解任意两个节点之间的最短距离，对于稠密图的效率高于执行 V 次 Dijkstra算法。
Floyd 算法可以处理负权边。
Floyd 算法号称只有 5行代码，我们来欣赏一下：
A*算法是一种静态路网中求解最短路径最有效的直接搜索方法。
A*算法是启发式算法，采用最佳优先（Best-first）搜索策略，基于估价函数对每个搜索位置的评估结果，猜测最好的位置优先进行搜索。
A*算法极大地减少了低质量的搜索路径，因而搜索效率很高，比传统的路径规划算法实时性更高、灵活性更强；但是，A*算法找到的是相对最优路径，不是绝对的最短路径，适合大规模、实时性高的问题。
NetworkX 提供了丰富的最短路径函数，除了常见的 Dijkstra 算法、Bellman-ford 算法、Floyd Warshall 算法和 A*算法，还有 Goldbery-Radzik 算法和 Johnson 算法。其中，Bellman-ford 算法函数使用的是队列改进算法，即以 SPFA 算法实现。
其中，最基本的求解最短路径函数 shortest() 和 最短路径长度 shortest_path_length() 是 ‘dijkstra’ 算法和 ‘bellman-ford’ 算法的集成接口，可以通过 method='dijkstra' 选择不同的算法。
shortest_path(G, source=None, target=None, weight=None, method='dijkstra') shortest_path_length(G, source=None, target=None, weight=None, method='dijkstra')
主要参数：
NetworkX 中关于 Dijkstra 算法提供了 13 个函数，很多函数的功能是重复的。这里只介绍最基本的函数 dijkstra_path() 和 dijkstra_path_length()。
dijkstra_path() 用于计算从源到目标的最短加权路径，dijkstra_path_length() 用于计算从源到目标的最短加权路径长度。
dijkstra_path(G, source, target, weight='weight') dijkstra_path_length(G, source, target, weight='weight')
主要参数：
NetworkX 中关于 Bellman-Ford 算法提供了多个函数，这里只介绍最基本的函数 bellman_ford_path() 和 bellman_ford_path_length()。
bellman_ford_path() 用于计算从源到目标的最短加权路径，bellman_ford_path_length() 用于计算从源到目标的最短加权路径长度。
bellman_ford_path(G, source, target, weight='weight') bellman_ford_path_length(G, source, target, weight='weight')
主要参数：
