python中最短路径问题的示例分析

小编给大家分享一下python中最短路径问题的示例分析，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！

说明

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

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

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

实例

def findMin(row):    minL = max(row)    for i in row:        if i != -1 and minL > i:            minL = i    return minLdef 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()

看完了这篇文章，相信你对“Python中最短路径问题的示例分析”有了一定的了解，如果想了解更多相关知识，欢迎关注编程网Python频道，感谢各位的阅读！