赞
踩
图算法在解决网络和路径问题中发挥着关键作用,而Dijkstra算法、Floyd-Warshall算法和Bellman-Ford算法是图算法家族中的重要成员。
Dijkstra算法(贪心)
解决非负权边(也就是只能为正边)图中最短路径问题的贪心算法,通过逐步选择当前最短路径的节点,求解从给定起始节点到其他所有节点的最短路径(找到单源最短路径的贪心算法)。
简而言之,从一个节点到所有其他节点的最短路径。
Floyd-Warshall算法(动态规划)
解决有向图中所有节点对最短路径问题的动态规划算法,通过逐步优化节点对之间的最短路径,适用于权值为正或负的有向图(全源最短路径)。
简而言之,所有顶点间的最短路径,允许负权边。
Bellman-Ford算法
解决带有负权边图中最短路径问题的动态规划算法,通过对所有边进行松弛操作,逐步优化从源节点到其他所有节点的最短路径。特别擅长检测负权回路。
简而言之,Bellman-Ford算法可以求带负权边的图的单源最短路,并且可以判断图是否存在负环。存在负环的图求最短路是没有意义的因为它的路径权会无限缩小
网络路由: 在计算机网络中,Dijkstra算法可以用于找到数据包从源节点到目标节点的最短路径,确保网络通信的效率和快速传输。
交通规划: 在城市交通规划中,Dijkstra算法可以用于寻找最短路径,帮助驾驶导航系统计算最快到达目的地的路线。
航空业: 航空公司可以使用Dijkstra算法来规划最短的航班路径,以减少燃料消耗和飞行时间。
电信网络: 运营商可以利用Dijkstra算法来规划光纤或电信线路的布局,确保信息传输的最短路径。
物流和配送: 在物流行业,Dijkstra算法可用于规划货物运输的最短路径,降低运输成本和时间。
Dijkstra算法是一种贪心算法,通过选择当前最短路径的节点,并更新其邻居的路径长度,逐步确定起始节点到其他节点的最短路径。
即每次选择当前最短路径,逐步构建最短路径集合。通过不断更新节点的距离来逼近最短路径。
以交通规划为例子,有ABCDEF6个地方,权重表示距离(公里),我们想要从城市 A 出发,找到最短路径到达城市 F。我们可以使用Dijkstra算法进行计算。
重复步骤3和步骤4,直到所有城市都被访问过。
手写的A分别到BCDEF的最短路径结果
import networkx as nx import matplotlib.pyplot as plt # 创建图 G = nx.Graph() # 添加节点和边 edges = [('A', 'B', {'weight': 5}), ('A', 'D', {'weight': 1}), ('B', 'C', {'weight': 2}), ('B', 'D', {'weight': 4}), ('B', 'E', {'weight': 3}), ('C', 'F', {'weight': 3}), ('D', 'E', {'weight': 7}), ('E', 'F', {'weight': 6})] G.add_edges_from(edges) # 计算最短路径 shortest_path = nx.shortest_path(G, source='A', target='F', weight='weight') print("Shortest Path:", shortest_path) shortest_distance = nx.shortest_path_length(G, source='A', target='F', weight='weight') print("Shortest Distance:", shortest_distance) # 绘制图形 pos = {'A': (0, 0), 'B': (1, 0), 'C': (2, 0), 'D': (0, -1), 'E': (1, -1), 'F': (2, -1)} nx.draw(G, pos, with_labels=True, font_weight='bold', node_size=700, node_color='skyblue', font_color='black', font_size=8) # 绘制最短路径 edges_in_shortest_path = [(shortest_path[i], shortest_path[i + 1]) for i in range(len(shortest_path) - 1)] nx.draw_networkx_edges(G, pos, edgelist=edges_in_shortest_path, edge_color='red', width=2) # 添加边的权重标签 edge_labels = nx.get_edge_attributes(G, 'weight') nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels) # 显示图形 plt.show()
得到的结果就是1.3.1的图。
时间复杂度
Dijkstra算法的时间复杂度取决于图的规模,通常为O(V^2),其中V是节点的数量。
然而,通过使用优先队列等数据结构,可以将时间复杂度优化到O((V + E) * log(V)),其中E是边的数量
空间复杂度: 在最坏情况下,空间复杂度为O(V),其中V是顶点数。
以1.3为例,在给定的例子中,有 6 个顶点(A、B、C、D、E、F)和 8 条边,所以 V = 6,E = 8。这样,时间复杂度可以表示为 O((6 + 8) * log(6)),空间复杂度为 O(6)。
注意:Dijkstra算法无法解决有负边的情况。
这儿有个视频讲得很好:https://www.youtube.com/watch?v=oNI0rf2P9gE
区别与找到单源最短路径的贪心算法(Dijkstra), Floyd-Warshall是全源最短路径,并且可以出现负边。
网络路由算法: 在计算机网络中,Floyd-Warshall算法可用于确定不同点的最短路径,以帮助路由数据包通过网络。
交通规划: 在城市交通规划中,Floyd-Warshall算法可以用于计算不同地点的最短路径,以优化交通流和减少拥堵。
航空业: 航班调度和路径规划中,Floyd-Warshall算法可以帮助确定不同城市之间的最短飞行路径。
电信网络规划: 在电信领域,Floyd-Warshall算法可以用于确定通信网络中不同节点之间的最短路径,以提高数据传输效率。
物流和运输: 在物流和运输领域,Floyd-Warshall算法可以用于计算多个货物从生产地到目的地的最短路径,以降低运输成本。
城市规划: 在城市规划中,Floyd-Warshall算法可以用于分析城市中不同地点之间的最短路径,以优化基础设施和服务的布局。
Floyd-Warshall算法的设计思路是通过不断迭代更新路径信息,从而找到图中所有点对之间的最短路径。
算法的核心思想是逐步优化路径长度矩阵,直到找到所有点对之间的最短路径。这样,算法适用于解决所有点对之间的最短路径问题,而不需要针对每一对点单独计算。
A、B、C分别表示三个城市,边的权重表示从一个城市到另一个城市的路径长度。给定的邻接矩阵表示城市之间的路径长度,其中∞表示两城市之间没有直接路径。现在要找出每个城市到每个城市的最短距离。
有矩阵:
构造一个距离矩阵
A | B | C | |
---|---|---|---|
A | 0 | 4 | 2 |
B | ∞ | 0 | 1 |
C | 2 | 1 | 0 |
初始的前驱矩阵(Predecessor Matrix)如下(-1表示无前驱节点):
A | B | C | |
---|---|---|---|
A | -1 | -1 | -1 |
B | -1 | -1 | -1 |
C | -1 | -1 | -1 |
现在,我们开始使用Floyd-Warshall算法的迭代过程。
A | B | C | |
---|---|---|---|
A | 0 | 4 | 2 |
B | ∞ | 0 | 1 |
C | 2 | 1 | 0 |
在这一轮中,没有找到更短的路径,所以Predecessor Matrix保持不变。
A | B | C | |
---|---|---|---|
A | 0 | 4 | 2 |
B | ∞ | 0 | 1 |
C | 2 | 1 | 0 |
在这一轮中,没有找到更短的路径,所以Predecessor Matrix保持不变。
A | B | C | |
---|---|---|---|
A | 0 | 3 | 2 |
B | 3 | 0 | 1 |
C | 2 | 1 | 0 |
最终,我们得到了最终的距离矩阵和前驱节点矩阵:
Final Distance Matrix:
A | B | C | |
---|---|---|---|
A | 0 | 3 | 2 |
B | 3 | 0 | 1 |
C | 2 | 1 | 0 |
Predecessor Matrix:
A | B | C | |
---|---|---|---|
A | -1 | 2 | -1 |
B | 2 | -1 | -1 |
C | -1 | -1 | -1 |
import numpy as np # 定义无穷大 INF = float('inf') # 定义图的邻接矩阵 graph = np.array([[0, 4, 2], [INF, 0, 1], [2, 1, 0]]) # 获取节点个数 n = len(graph) # 初始化距离矩阵和前驱节点矩阵 distance_matrix = graph.copy() predecessor_matrix = np.full((n, n), -1) # Floyd-Warshall算法 for k in range(n): for i in range(n): for j in range(n): if distance_matrix[i][j] > distance_matrix[i][k] + distance_matrix[k][j]: distance_matrix[i][j] = distance_matrix[i][k] + distance_matrix[k][j] predecessor_matrix[i][j] = k # 打印最终的距离矩阵和前驱节点矩阵 print("Final Distance Matrix:") print(distance_matrix) print("\nPredecessor Matrix:") print(predecessor_matrix)
运行结果:
注意:
i为行,j为列,先行后列。
自己到自己始终是0,没有任何路径比自己到自己还小的,因此正对角线没有意义直接不看。
首先标出第k行和第k列(k>=1),对角线不参与计算,留出空白与第一行和第一列相加比大小。
借助A间接到达其它顶点
将第一列和第一行和对角线标上特殊的颜色,此时我们要计算特别的空白的值,是否有
直接来看例子:
例如,d(21)+d(13)=无穷+2>d(23),因此d(23)=1不动;如果d(21)+d(13)=无穷+2<d(23),那么d(23)就要更新。
以此类推…d(32)同理。
借助B间接到达其它顶点
同上。
借助C间接到达其它顶点
这里可以看到,
d(13)+d(32)=2+1=3 < d(12)=4
d(23)+d(31)=2+1=3 < d(21)=∞
因此更新值。这是最终结果:
时间复杂度: O(V^3)
V 是图中的顶点数。
由于算法需要计算所有顶点对之间的最短路径,它的时间复杂度是三重循环的结果。
空间复杂度: O(V^2)
Floyd-Warshall算法的空间复杂度为O(V^2),这是因为算法需要存储每一对顶点之间的最短路径长度。对于每一对顶点(i, j),我们只需使用O(1)的空间来存储它们之间的最短路径长度,但由于存在V × V对的顶点,所以总的空间复杂度为O(V^2)。
参考youtube的视频:https://www.youtube.com/watch?v=FtN3BYH2Zes&t=10s
这是目前为止我觉得讲得最清楚的了。
场景: 银行资金流动。
解释: 在金融系统中,资金流动可能涉及到费用或成本,而这些成本可能是负数。Bellman-Ford算法可以用于计算最短路径,考虑到负数成本,以便选择费用最小的路径。
场景: 网络路由变化较少。
解释: 在计算机网络中,路由信息可能会发生变化,但这些变化可能是相对较小的,例如一些路由器的状态发生变化。Bellman-Ford算法适用于这种情况,因为它能够在图变化较小的情况下快速适应。
场景: 城市之间的交通网络。
解释: 考虑一个较小的城市交通网络,其中城市是节点,道路是边。由于规模较小,Bellman-Ford算法可能在计算城市之间最短路径时比Dijkstra算法更有效。
场景: 金融交易的环路检测。
解释: 在金融交易中,如果存在环路,可能导致无限循环的负债。Bellman-Ford算法可以用于检测是否存在这样的负权环。
如果一个图没有负权环,从一点到另外一点的最短路径,最多经过所有的V个顶线,有V-1条边,否则,存在顶点经过了两次,既存在负权环。
算法过程:
初始化: 首先,将源节点到所有其他节点的距离初始化为无穷大,将源节点的距离初始化为0。这个步骤确保了在算法开始时,只有源节点的距离是已知的,其他节点的距离是未知的。
(图来自Abdul Bari也就是上面那个视频)
松弛操作: 算法通过多轮的松弛操作来逐步更新节点之间的最短路径。对于每一条边 (u, v),尝试通过该边松弛节点 v 的距离。即,检查是否通过节点 u 可以找到一条到节点 v 更短的路径。
多轮迭代: Bellman-Ford算法采用多轮迭代的方式,每一轮都尝试通过所有边进行松弛操作。这是为了确保在最坏情况下,算法能够找到从源节点到所有其他节点的最短路径。通常需要进行 |V| - 1 轮迭代,其中 |V| 是节点的数量。
(图来自Abdul Bari)
检测负权环: 在进行 |V| - 1 轮迭代之后,算法会检查是否存在负权环。如果在第 |V| 次迭代中,仍然可以通过边松弛节点的距离,说明图中存在负权环。存在负权环意味着没有有限的最短路径,因为可以通过环路反复减小路径长度。
问题:
假设你是一位金融分析师,有一系列不同的金融资产,每个资产之间存在交易关系,而每个交易都有相关的成本。你希望找到从特定资产到其他所有资产的最短路径,考虑到每个交易的成本。使用Bellman-Ford算法解决这个实际金融问题。
具体表述如下:
transactions = [
(1, 2, 6),
(1, 3, 5),
(1, 4, 5),
(2, 5, -1),
(3, 2, -2),
(4, 3, -2),
(3, 5, 1),
(4, 6, -1),
(5, 7, 3),
(6, 7, 3)
]
每个元组的三个值分别表示从一个资产到另一个资产的交易成本。Bellman-Ford算法用于找到从指定的起始资产到所有其他资产的最短路径,考虑到每个交易的成本。在这个特定的例子中,起始节点是资产 1。
def bellman_ford(graph, start): # 初始化距离数组 n = max(max(u, v) for u, v, _ in graph) + 1 dist = [float('inf')] * n dist[start] = 0 # 多轮迭代 for _ in range(n - 1): # 对每条边进行松弛操作 for u, v, weight in graph: if dist[u] + weight < dist[v]: dist[v] = dist[u] + weight # 输出每一轮迭代后的距离情况 print(f"Iteration {_ + 1}: {dist}") # 检查是否存在负权环 for u, v, weight in graph: if dist[u] + weight < dist[v]: print("图中存在负权环,无法找到最短路径") return None return dist # 示例图的边和权重表示 graph_example = [ (1, 2, 6), (1, 3, 5), (1, 4, 5), (2, 5, -1), (3, 2, -2), (4, 3, -2), (3, 5, 1), (4, 6, -1), (5, 7, 3), (6, 7, 3) ] # 运行Bellman-Ford算法 start_node = 1 result = bellman_ford(graph_example, start_node) # 输出最终的最短路径结果 print("最终的最短路径结果:", result)
运行结果:
时间复杂度
Bellman-Ford算法的时间复杂度是O(V * E),其中V是顶点数,E是边数。
空间复杂度
空间复杂度是O(V),主要用于存储距离数组和其他辅助数据结构。
欢迎关注:https://blog.csdn.net/hanhanwanghaha
Dijkstra算法(贪心)
优点:
针对单源最短路径问题的正权重图,Dijkstra算法的效率较高。
适用于图中边的权重为非负数的情况。
缺点:
无法处理带有负权重边的图,因为它基于贪心策略,每一步都选择当前最短路径,而负权重可能导致在后续的步骤中发现更短的路径。
对于稀疏图,使用优先队列实现的Dijkstra算法可能更有效。
Floyd-Warshall算法(动态规划)
优点:
适用于包含负权重边的图。
能够计算任意两点之间的最短路径。
缺点:
时间和空间复杂度较高,不适用于大规模图。
不适合处理动态图的情况,因为每次都要重新计算所有顶点对之间的最短路径。
Bellman-Ford算法
优点:
能够处理带有负权重边的图,并能够检测负权重环的存在。
适用于单源最短路径问题。
缺点:
时间复杂度较高,为O(V * E),其中V是顶点数,E是边数。
在一般情况下,对于正权重图,性能可能不如Dijkstra算法。
不如Floyd-Warshall算法适用于所有顶点对的最短路径问题。
使用范围:
使用Dijkstra算法时,图应该是无负权重的。
使用Floyd-Warshall算法时,可以处理带有负权重边的图,但不适用于大规模图。
使用Bellman-Ford算法时,可以处理带有负权重边的图,并能够检测负权重环。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。