• 技术文章 >Python技术 >Python基础教程

    python最短路径问题的介绍

    小妮浅浅小妮浅浅2021-09-16 09:36:13原创2812

    说明

    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<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学习指路:python基础教程

    本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。

    专题推荐:python最短路径
    上一篇:Python Dijkstra算法是什么 下一篇:python Bellman-Ford算法是什么

    相关文章推荐

    • python return和yield有什么不同• python迭代器的取值方法• python迭代器的优缺点• python使用Pyecharts绘制疫情分布图• 如何查看python解释器的路径• python用户输入的方法• python if-elif-else语句是什么• python列表中if语句的用途• Python f-string字符串格式化的介绍• Python Dijkstra算法是什么

    全部评论我要评论

    © 2021 Python学习网 苏ICP备2021003149号-1

  • 取消发布评论
  • 

    Python学习网