导语:
本文主要介绍了关于python最短路径问题的介绍的相关知识,包括最短路径分析,以及单源最短路径问题这些编程知识,希望对大家有参考作用。
说明
1、最短路径问题是图论研究中的一个经典算法问题,用于计算一个顶点到另一个顶点的最短路径。
2、最短路径问题有几种形式:
确定到起点的最短路径,确定到终点的最短路径,确定到起点和终点的最短路径,全局最短路径问题。
路径长度将每个顶点到相邻顶点的长度计为1,而不是两个顶点之间的道路距离 - 两个顶点之间的道路距离是连接边的右侧。
实例
def findMin(row):
minL = max(row)
for i in row:
if i != -1 and minL > i:
minL = i
return minL
def initRow(row, plus):
r = []
for i in row:
if i != -1:
i += plus
r.append(i)
return r
def getMinLen(table, e, t):
count = len(table) - 1
startPoint = 1
#记录原点到各点最短距离 初始值为-1,即不可达
lenRecord = list((-1 for i in range(count+1)))
lenRecord[startPoint] = 0
#记录每次循环的起点
points = [startPoint]
#已得到最短距离的点
visited = set()
while len(points)>0:
#当前起点
curPoint = points.pop()
#原点到当前起点的距离
curLen = lenRecord[curPoint]
#当前起点到各点的距离
curList = initRow(table[curPoint], t)
#当前起点到各点的最短距离
curMin = findMin(curList)
visited.add(curPoint)
idx = 0
while idx<count:
idx += 1
#当前点不可达或到当前点的最短距离已计算出 则跳过
if curList[idx] == -1 or idx in visited:
continue
#记录距离当前起点最近的点作为下次外层循环的起点
if curList[idx] == curMin:
points.append(idx)
#如果从原点经当前起点curPoint到目标点idx的距离更短,则更新
if lenRecord[idx] == -1 or lenRecord[idx] > (curLen+curList[idx]):
lenRecord[idx] = curLen+curList[idx]
return lenRecord[e]
def processInput():
pointCnt, roadCnt, jobCnt = (int(x) for x in raw_input().split())
table = []
for i in range(pointCnt+1):
table.append([-1] * (pointCnt+1))
for i in range(roadCnt):
(x, y, w) = (int(n) for n in raw_input().split())
if table[x][y] == -1 or table[x][y] > w:
table[x][y] = w
table[y][x] = w
res = []
for i in range(jobCnt):
e, t = (int(x) for x in raw_input().split())
res.append(getMinLen(table, e, t))
for i in res:
print(i)
processInput()
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。
本文为原创文章,版权归知行编程网所有,欢迎分享本文,转载请保留出处!
你可能也喜欢
- ♥ 一篇文章看懂py2/py3编码问题12/26
- ♥ python字符类的使用01/14
- ♥ 如何获取python字符串的值10/10
- ♥ 相见恨晚的 Python 内置库:itertools02/18
- ♥ 详细讲解如何在python中将ASCII码转换为字符12/20
- ♥ python生成器调用方法抛出异常11/05
内容反馈