百度一下首页网页百度,seo网站技术培训,本溪网站建设,wordpress管理面板显示错乱Floyd算法
Floyd算法又称为Floyd-Warshell算法#xff0c;其实Warshell算法是离散数学中求传递闭包的算法#xff0c;两者的思想是一致的。Floyd算法是求解多源最短路时通常选用的算法#xff0c;经过一次算法即可求出任意两点之间的最短距离#xff0c;并且可以处理有负权…Floyd算法
Floyd算法又称为Floyd-Warshell算法其实Warshell算法是离散数学中求传递闭包的算法两者的思想是一致的。Floyd算法是求解多源最短路时通常选用的算法经过一次算法即可求出任意两点之间的最短距离并且可以处理有负权边的情况但无法处理负权环算法的时间复杂度是 O ( n 3 ) O(n^3) O(n3)空间复杂度是 O ( n 2 ) O(n^2) O(n2)。
import numpy as npdef floyd(adjacent_matrix, source, target)::param adjacent_matrix: 图邻接矩阵:param source: 起点:param target: 终点:return: shortest_pathnum_node len(adjacent_matrix)# 计算矩阵D记录顶点间的最小路径例如D[0][3] 10说明顶点0 到 3 的最短路径为10矩阵P记录顶点间最小路径中的中转点例如P[0][3] 1 说明0 到 3的最短路径轨迹为0 - 1 - 3。distance np.zeros(shape(num_node, num_node), dtypenp.int_)path np.zeros(shape(num_node, num_node), dtypenp.int_)for v in range(num_node):for w in range(num_node):distance[v][w] adjacent_matrix[v][w]path[v][w] w# 弗洛伊德算法的核心部分for k in range(num_node): # k为中间点for v in range(num_node): # v 为起点for w in range(num_node): # w为起点if distance[v][w] (distance[v][k] distance[k][w]):distance[v][w] distance[v][k] distance[k][w]path[v][w] path[v][k]print(np.asarray(path))shortest_path [source]k path[source][target]while k ! target:shortest_path.append(k)k path[k][target]shortest_path.append(target)return shortest_pathif __name__ __main__:M 1e6adjacent_matrix [[0, 12, M, M, M, 16, 14],[12, 0, 10, M, M, 7, M],[M, 10, 0, 3, 5, 6, M],[M, M, 3, 0, 4, M, M],[M, M, 5, 4, 0, 2, 8],[16, 7, 6, M, 2, 0, 9],[14, M, M, M, 8, 9, 0],]shortest_path floyd(adjacent_matrix, 0, 3)print(shortest_path)# [0, 6, 3, M, M, M],# [6, 0, 2, 5, M, M],# [3, 2, 0, 3, 4, M],# [M, 5, 3, 0, 5, 3],# [M, M, 4, 5, 0, 5],# [M, M, M, 3, 5, 0]适应场景
Floyd-Warshall算法由于其 O ( n 3 ) O(n^3) O(n3)的时间复杂度适用于节点数比较少且图比较稠密的情况。对于边数较少的稀疏图使用基于边的算法如Dijkstra或Bellman-Ford通常会更高效。
