python最短路径问题的介绍

说明

1、最短路径问题是图论研究中的经典算法问题，用于计算从一个顶点到另一个顶点的最短路径。

2、最短路径问题有几种形式：确定起点的最短路径，确定终点的最短路径，确定起点和终点的最短路径，全局最短路径问题。

路径长度是将每个顶点到相邻顶点的长度记为1，而不是指两个顶点之间的道路距离——两个顶点之间的道路距离是连接边的权利。

实例

deffindMin(row):
minL=max(row)
foriinrow:
ifi!=-1andminL>i:
minL=i
returnminL
definitRow(row,plus):
r=[]
foriinrow:
ifi!=-1:
i+=plus
r.append(i)
returnr

defgetMinLen(table,e,t):
count=len(table)-1
startPoint=1
#记录原点到各点最短距离初始值为-1，即不可达
lenRecord=list((-1foriinrange(count+1)))
lenRecord[startPoint]=0
#记录每次循环的起点
points=[startPoint]
#已得到最短距离的点
visited=set()
whilelen(points)>0:
#当前起点
curPoint=points.pop()
#原点到当前起点的距离
curLen=lenRecord[curPoint]
#当前起点到各点的距离
curList=initRow(table[curPoint],t)
#当前起点到各点的最短距离
curMin=findMin(curList)
visited.add(curPoint)
idx=0
whileidx<count:
idx+=1
#当前点不可达或到当前点的最短距离已计算出则跳过
ifcurList[idx]==-1oridxinvisited:
continue
#记录距离当前起点最近的点作为下次外层循环的起点
ifcurList[idx]==curMin:
points.append(idx)
#如果从原点经当前起点curPoint到目标点idx的距离更短，则更新
iflenRecord[idx]==-1orlenRecord[idx]>(curLen+curList[idx]):
lenRecord[idx]=curLen+curList[idx]
returnlenRecord[e]

defprocessInput():
pointCnt,roadCnt,jobCnt=(int(x)forxinraw_input().split())
table=[]
foriinrange(pointCnt+1):
table.append([-1]*(pointCnt+1))
foriinrange(roadCnt):
(x,y,w)=(int(n)forninraw_input().split())
iftable[x][y]==-1ortable[x][y]>w:
table[x][y]=w
table[y][x]=w
res=[]
foriinrange(jobCnt):
e,t=(int(x)forxinraw_input().split())
res.append(getMinLen(table,e,t))
foriinres:
print(i)

processInput()

以上就是python最短路径问题的介绍，希望对大家有所帮助。更多python学习指路：python基础教程

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。