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

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

成都创新互联-专业网站定制、快速模板网站建设、高性价比普宁网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式普宁网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖普宁地区。费用合理售后完善，10年实体公司更值得信赖。

说明

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 (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中最短路径问题的示例分析”有了一定的了解，如果想了解更多相关知识，欢迎关注创新互联行业资讯频道，感谢各位的阅读！