python最短路径问题的介绍

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()