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

    python最短路径问题的介绍

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

    说明

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

    2、最短路径问题有几种形式:确定起点的最短路径,确定终点的最短路径,确定起点和终点的最短路径,全局最短路径问题。

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

    实例

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    50

    51

    52

    53

    54

    55

    56

    57

    58

    59

    60

    61

    62

    63

    64

    65

    66

    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学习网