前言
弗洛伊德算法(Floyd)
- 初始化路径矩阵：使用图的邻接矩阵初始化路径矩阵，其中路径矩阵表示任意两个顶点之间的最短路径长度
- 三重循环： 对于每一对顶点 和 ，遍历所有中间顶点 ，检查是否存在通过 的路径比直接路径更短。 如果是，则更新路径矩阵中的值
- 最终路径矩阵： 在完成所有循环后，路径矩阵将包含所有顶点对之间的最短路径长度
弗洛伊德算法的时间复杂度为 ( )，其中 是顶点的数量。这个算法适用于有向图和无向图，可以处理带有负权边的图，但如果图中存在负权回路，则最短路径可能无穷大。
迪杰斯特拉( Dijkstra)
- 初始化：将起始顶点的最短路径长度设置为0，其他顶点的最短路径长度设置为无穷大。创建一个集合（通常是优先队列）存储未访问的顶点
- 选择最短路径：从未访问的顶点中选择当前最短路径长度的顶点，将其标记为已访问
- 更新相邻顶点的距离：对于当前选定的顶点，更新其相邻顶点的最短路径长度。如果通过当前选定的顶点到达相邻顶点的路径比已知的最短路径短，就更新最短路径
- 重复步骤2和3：重复选择最短路径和更新相邻顶点的距离的步骤，直到所有顶点都被访问过或者目标顶点的最短路径确定
Dijkstra（迪杰斯特拉）算法是一种用于计算图中单源最短路径的贪心算法，是一种有效的最短路径算法，但它也有一些缺点：不能处理负权边和负权回路，且在某些情况下复杂度较高，适用于单源最短路径问题
代码实现
接下来将采用此有向图实现弗洛伊德、迪杰斯特拉求解最短路径
弗洛伊德算法(Floyd)
V = 6 # 顶点的个数
INF = 99999 # 设定一个最大值
P = [[0]*V for i in range(V)] # 记录各个顶点之间的最短路径
# 有向加权图中各个顶点之间的路径信息
graph = [[0, 2, 1, 4, INF, INF],
[INF, 0, INF, 3, INF, 2],
[INF, INF, 0, INF, 3, INF],
[INF, INF, INF, 0, INF, 1],
[INF, INF, INF, 4, 0, 2],
[INF, INF, INF, INF, INF, 0]]
# 中序递归输出各个顶点之间最短路径的具体线路
def printPath(i,j):
k = P[i][j]
if k == 0:
return;
printPath(i , k)
print("%d-" % (k + 1) , end='')
printPath(k , j)
# 输出各个顶点之间的最短路径
def printMatrix(graph):
for i in range(V):
for j in range(V):
if j == i:
continue
print("%d - %d: 最短路径为:"%(i + 1, j + 1) , end='')
if graph[i][j] == INF:
print("INF")
else:
print(graph[i][j] , end='')
print("，依次经过：%d-"%(i+1) , end='')
# 调用递归函数
printPath(i , j)
print(j + 1)
# 实现弗洛伊德算法,graph[][V] 为有向加权图
def floydWarshall(graph):
# 遍历每个顶点，将其作为其它顶点之间的中间顶点，更新 graph 数组
for k in range(V):
for i in range(V):
for j in range(V):
# 如果新的路径比之前记录的更短，则更新 graph 数组
if graph[i][k] + graph[k][j] < graph[i][j]:
graph[i][j] = graph[i][k] + graph[k][j]
# 记录此路径
P[i][j] = k
# 输出各个顶点之间的最短路径
printMatrix(graph)
floydWarshall(graph)
代码使用弗洛伊德算法来求解有向加权图中各个顶点之间的最短路径。下面是对这段代码的简要解释：
定义变量：
V：顶点的数量，这里设定为6
INF：表示正无穷大，用于初始化图中不存在的边的权重
P：一个二维数组，用于记录各个顶点之间的最短路径中的中间顶点
graph：有向加权图中各个顶点之间的路径信息，以邻接矩阵的形式表示。
printPath函数：
递归函数，用于中序递归输出各个顶点之间最短路径的具体线路。
给定起点和终点，递归地找到中间经过的顶点，输出路径
printMatrix函数：
输出各个顶点之间的最短路径。
对于每一对顶点i和j，输出其最短路径的长度以及路径的具体线路。
floydWarshall函数：
弗洛伊德算法的实现。
通过三层循环，遍历每个顶点作为中间顶点，更新图中所有顶点对之间的最短路径
如果通过中间顶点k能够缩短顶点对(i, j)的路径长度，就更新最短路径和记录中间顶点
迪杰斯特拉( Dijkstra)
class Dijkstra:
def __init__(self, graph, goal):
self.graph = graph
self.goal = goal
self.open_list = {} # 以open_list初始化为一个空字典，keys为节点‘1’‘2’...，values为distance既从'1'到该点的实际代价
self.closed_list = {} # closed_list初始化为空字典，键和值与open_list相同
self.open_list['1'] = 0 # 初始节点为‘1’且‘1’到‘1’的值为‘0’，将其传入到open_list列表中
self.parent = {'1':None} # 初始父节点为字典型，初始键为‘1’值为None，其中键是子节点，值是父节点
self.min_dis = None # 初始最短路径长度为None
def shortest_path(self):
while True:
if self.open_list is None:
print('搜索失败，结果!')
break
distance, min_node = min(zip(self.open_list.values(), self.open_list.keys())) # 取出距离最小的节点
self.open_list.pop(min_node) # 将其从open_list 中去除
self.closed_list[min_node] = distance # 将节点加入closed_list中
if min_node == self.goal: # 如果节点为终点
self.min_dis = distance
shortest_path = [self.goal] # 记录从终点回溯的路径
father_node = self.parent[self.goal]
while father_node != '1':
shortest_path.append(father_node)
father_node = self.parent[father_node]
shortest_path.append('1')
print(shortest_path[::-1]) # 逆序
print('最短路径长度:{}'.format(self.min_dis))
print('找到最短路径，结束!')
return shortest_path[::-1], self.min_dis # 返回最短路径和最短路径长度
for node in self.graph[min_node].keys(): # 遍历当前节点的邻接节点
if node not in self.closed_list.keys(): # 邻接节点不在closed_list中
if node in self.open_list.keys(): # 如果节点在open_list中
if self.graph[min_node][node] + distance < self.open_list[node]:
self.open_list[node] = distance + self.graph[min_node][node] # 更新节点值
self.parent[node] = min_node
else: # 如果节点不在open_list中
self.open_list[node] = distance + self.graph[min_node][node] # 计算节点的值,并加入open_list 中
self.parent[node] = min_node # 更新继承关系
代码实现Dijkstra算法来寻找有向图中两个节点之间的最短路径。下面是对代码的简要解释：
初始化：
__init__方法初始化Dijkstra类的实例。接受图和目标节点作为参数
graph是一个字典，表示有向图的邻接关系，其中键是节点，值是字典，表示该节点与其邻接节点以及对应的权重
goal是目标节点，即要找到最短路径的终点
open_list是一个字典，用于存储待处理的节点及其距离，初始时包含起始节点 '1'，距离为0
closed_list是一个字典，用于存储已经处理过的节点及其距离
parent是一个字典，记录每个节点的父节点，初始时 '1' 的父节点为 None
min_dis用于记录最短路径的长度，初始值为 None
shortest_path方法：
使用while循环进行迭代，直到找到目标节点或者无法继续搜索
在循环中，通过比较open_list中节点的距离，找到距离最小的节点，并将其从open_list中移除，加入到closed_list中
如果最小节点为目标节点，回溯得到最短路径，并输出路径和长度
遍历当前节点的邻接节点，更新节点值和父节点关系
返回结果：
最短路径和最短路径长度通过return语句返回。
注意事项：
如果open_list为空，表示无法找到最短路径，输出搜索失败
代码中使用了zip和min函数来找到距离最小的节点，以及逆序输出最短路径
if __name__ == '__main__':
g = {'1':{'2':2, '3':1, '4':4},
'2':{'4':3, '6':2},
'3':{'5':3},
'4':{'6':1},
'5':{'4':4, '6':2}} # 有向
goal = '5' # 默认起点为‘1’，此为终点
dijkl = Dijkstra(g, goal)
dijkl.shortest_path()
如果你对类似于这样的文章感兴趣。
欢迎关注、点赞、转发~