python中最短路徑問題的示例分析

小編給大家分享一下python中最短路徑問題的示例分析，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

說明

1、最短路徑問題是圖論研究中的經(jīng)典算法問題，用于計算從一個頂點到另一個頂點的最短路徑。

2、最短路徑問題有幾種形式：確定起點的最短路徑，確定終點的最短路徑，確定起點和終點的最短路徑，全局最短路徑問題。

路徑長度是將每個頂點到相鄰頂點的長度記為1，而不是指兩個頂點之間的道路距離——兩個頂點之間的道路距離是連接邊的權(quán)利。

實例

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
    #記錄每次循環(huán)的起點
    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
            #記錄距離當前起點最近的點作為下次外層循環(huán)的起點
            if curList[idx] == curMin:
                points.append(idx)
            #如果從原點經(jīng)當前起點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中最短路徑問題的示例分析”有了一定的了解，如果想了解更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！