【最短路

【最短路

文章目录

• • 1.前言
  • 2.代码实现
  • 3.参考资源

1.前言

最近在学习《交通网络均衡理论》这门课，我计划将其中的一些经典算法用Python实现，而后发布到这里来和大家交流，欢迎指正。

2.代码实现

'''
@Author: Michael 2022-09-16 16:48:22
This code is about Floyd-Warshall.'''
import copydef Floyd(mgraph,start,end):start,end = start-1,end-1 #目标及索引归一dis,prepoint = GetDisPoint(mgraph)print(f"各点间最短距离矩阵为（若值为{inf}则表示对应点间无通路）：\n{dis}")PathOut(dis,prepoint,start,end,inf)def GetDisPoint(mgraph):'''dis矩阵（此处矩阵均以列表存储，后面不在赘述）表示各点间最短路径prepoint矩阵用于存储路径前向点，其中-1表示i，j直连，初始假设各点均直连注意！！！若i,j无通路，则其前向点对应也为-1，因此利用前向点矩阵prepoin输出路径时，应先根据dis矩阵做初步判断'''dis = copy.deepcopy(mgraph)prepoint = [[-1 for i in range(len(mgraph))] for i in range(len(mgraph))] for k in range(len(mgraph)):for i in [i for i in range(len(mgraph)) if i != k]:for j in [i for i in range(len(mgraph)) if i != k]:if dis[i][j] > dis[i][k] + dis[k][j]:dis[i][j] = dis[i][k] + dis[k][j]prepoint[i][j] = kreturn dis,prepointdef RevTrace(start,end,prepoint,path=[]):'''逆向追踪寻找两点间通路，假设各点间均有通路'''if prepoint[start][end] == -1:path.append(end+1)else:mid = prepoint[start][end]RevTrace(start,mid,prepoint)RevTrace(mid,end,prepoint)return [start+1] + pathdef PathOut(dis,prepoint,start,end,inf):'''输出指定两点间最短路径'''if dis[start][end] == inf: print(f"\n其中{start+1} --> {end+1} 无通路")else:path = RevTrace(start,end,prepoint)print(f"\n其中{start+1} --> {end+1}\n最短路径长为：{dis[start][end]}\n最短路径为：{path}")start,end = 2,4 #目标起始点，用于输出某条路径
inf = 999 #此处表示极大值
mgraph = [[0,2,5,inf,inf,inf,inf],[inf,0,2,4,3,inf,inf],[inf,inf,0,1,inf,inf,inf],[inf,inf,inf,0,5,6,inf],[inf,inf,inf,inf,0,7,inf],[inf,inf,inf,inf,inf,0,inf],[inf,inf,3,8,inf,2,0]]Floyd(mgraph,start,end)

两种输出情况：

各点间最短距离矩阵为（若值为999则表示对应点间无通路）：
[[  0   2   4   5   5  11 999][999   0   2   3   3   9 999][999 999   0   1   6   7 999][999 999 999   0   5   6 999][999 999 999 999   0   7 999][999 999 999 999 999   0 999][999 999   3   4   9   2   0]]其中2 --> 4
最短路径长为：3
最短路径为：[2, 3, 4]

各点间最短距离矩阵为（若值为999则表示对应点间无通路）：
[[  0   2   4   5   5  11 999][999   0   2   3   3   9 999][999 999   0   1   6   7 999][999 999 999   0   5   6 999][999 999 999 999   0   7 999][999 999 999 999 999   0 999][999 999   3   4   9   2   0]]其中5 --> 3 无通路

3.参考资源

[1] 最短路径Floyd算法
[2] 史峰.组合优化理论与计算方法.
[3]【最短路–Dijkstra + Python】
[4] 夏伟怀等.运筹学.