精华内容
下载资源
问答
  • 本文给大家分享的是python 无向图最短路径算法:请各位大大指教,继续改进。(修改了中文字符串,使py2exe中文没烦恼),需要的朋友可以参考下
  • 最短路径算法Python代码
  • Dijkstra 最短路径算法 Python 实现问题描述使用 Dijkstra 算法求图中的任意顶点到其它顶点的最短路径(求出需要经过那些点以及最短距离)。以下图为例:算法思想可以使用二维数组来存储顶点之间边的关系首先需要用一...

    2ff34e647e2e3cdfd8dca593e17d9b0a.png

    Dijkstra 最短路径算法 Python 实现

    问题描述

    使用 Dijkstra 算法求图中的任意顶点到其它顶点的最短路径(求出需要经过那些点以及最短距离)。

    以下图为例:

    8854c11e50725e52699f1490f05b7c85.png

    算法思想

    可以使用二维数组来存储顶点之间边的关系

    50f943985771816bf90555f83599a72d.png

    首先需要用一个一维数组 dis 来存储 初始顶点到其余各个顶点的初始路程,以求 1 顶点到其它各个顶点为例:

    1cfe75af7fcc44afb7d3ac5a32c3a3e9.png

    将此时 dis 数组中的值称为最短路的“估计值”。

    既然是求 1 号顶点到其余各个顶点的最短路程,那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离 1 号顶点最近是 2 号顶点。当选择了 2 号顶点后,dis[2] 的值就已经从“估计值”变为了“确定值”,即 1 号顶点到 2 号顶点的最短路程就是当前 dis[2]值。为什么呢?因为目前离 1 号顶点最近的是 2 号顶点,并且这个图所有的边都是正数,那么肯定不可能通过第三个顶点中转,使得 1 号顶点到 2 号顶点的路程进一步缩短了。

    既然选了 2 号顶点,接下来再来看 2 号顶点有哪些出边。有 2->3 和 2->4 这两条边。先讨论通过 2->3 这条边能否让 1 号顶点到 3 号顶点的路程变短。也就是说现在比较 dis[3] 和 dis[2] + G[2][3]的大小。其中 dis[3] 表示 1 号顶点到 3 号顶点的路程。dis[2] + G[2][3] 中 dis[2] 表示 1 号顶点到 2 号顶点的路程,G[2][3] 表示 2->3 这条边。所以 dis[2] + G[2][3] 就表示从 1 号顶点先到 2 号顶点,再通过 2->3 这条边,到达 3 号顶点的路程。

    在本例中 dis[3] = 12,dis[2] + G[2][3] = 1 + 9 = 10,dis[3] > dis[2] + G[2][3],所以 dis[3] 要更新为 10。这个过程有个专业术语叫做“松弛”。即 1 号顶点到 3 号顶点的路程即 dis[3],通过 2->3 这条边松弛成功。这是 Dijkstra 算法的主要思想:通过“边”来松弛初始顶点到其余各个顶点的路程。

    同理通过 2->4(G[2][4]),可以将 dis[4]的值从 ∞ 松弛为 4(dis[4] 初始为 ∞,dis[2] + G[2][4] = 1 + 3 = 4,dis[4] > dis[2] + G[2][4],所以 dis[4] 要更新为 4)。

    刚才对 2 号顶点所有的出边进行了松弛。松弛完毕之后 dis 数组为:

    6866b815fc76aceb7f73e0f4f32c3f83.png

    接下来,继续在剩下的 3、4、5 和 6 号顶点中,选出离 1 号顶点最近的顶点。通过上面更新过 dis 数组,当前离 1 号顶点最近是 4 号顶点。此时,dis[4] 的值已经从“估计值”变为了“确定值”。下面继续对 4 号顶点的所有出边(4->3,4->5 和 4->6)用刚才的方法进行松弛。松弛完毕之后 dis 数组为:

    0653119e62d472216577add96059cb4c.png

    继续在剩下的 3、5 和 6 号顶点中,选出离 1 号顶点最近的顶点,这次选择 3 号顶点。此时,dis[3] 的值已经从“估计值”变为了“确定值”。对 3 号顶点的所有出边(3->5)进行松弛。松弛完毕之后 dis 数组为:

    ce11556828abd7349afbee865b664128.png

    继续在剩下的 5 和 6 号顶点中,选出离 1 号顶点最近的顶点,这次选择 5 号顶点。此时,dis[5] 的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边(5->4)进行松弛。松弛完毕之后 dis 数组为:

    b6add5bdf40f7d61bbd86122af679d12.png

    最后对 6 号顶点所有点出边进行松弛。因为这个例子中 6 号顶点没有出边,因此不用处理。到此,dis 数组中所有的值都已经从“估计值”变为了“确定值”。

    最终 dis 数组如下,这便是 1 号顶点到其余各个顶点的最短路径。

    368591e7a529e11b8e42383b05a69bfc.png

    总结一下刚才的算法。算法的基本思想是:每次找到离源点(上面例子的源点就是 1 号顶点)最近的一个顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径。基本步骤如下:将所有的顶点分为两部分:已知最短路程的顶点集合 P 和未知最短路径的顶点集合 Q。最开始,已知最短路径的顶点集合 P 中只有源点一个顶点。这里用一个 visited[ i ]数组来记录哪些点在集合 P 中。例如对于某个顶点 i,如果 visited[ i ]为 1 则表示这个顶点在集合 P 中,如果 visited[ i ]为 0 则表示这个顶点在集合 Q 中;

    设置源点 s 到自己的最短路径为 0 即 dis = 0。若存在源点有能直接到达的顶点 i,则把 dis[ i ]设为 G[s][ i ]。同时把所有其它(源点不能直接到达的)顶点的最短路径为设为 ∞;

    在集合 Q 的所有顶点中选择一个离源点 s 最近的顶点 u(即 dis[u] 最小)加入到集合 P。并考察所有以点 u 为起点的边,对每一条边进行松弛操作。例如存在一条从 u 到 v 的边,那么可以通过将边 u->v 添加到尾部来拓展一条从 s 到 v 的路径,这条路径的长度是 dis[u] + G[u][v]。如果这个值比目前已知的 dis[v] 的值要小,我们可以用新值来替代当前 dis[v] 中的值;

    重复第 3 步,如果集合 Q 为空,算法结束。最终 dis 数组中的值就是源点到所有顶点的最短路径

    Dijkstra 算法不能应用于有负权重的图

    Dijkstra 时间复杂度为 O(N2)

    Python 实现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

    50def (G, start):

    start = start - 1

    inf = float('inf')

    node_num = len(G)

    visited = [0] * node_num

    dis = {node: G[start][node] for node in range(node_num)}

    parents = {node: -1 for node in range(node_num)}

    # 起始点加入进 visited 数组

    visited[start] = 1

    # 最开始的上一个顶点为初始顶点

    last_point = start

    for i in range(node_num - 1):

    # 求出 dis 中未加入 visited 数组的最短距离和顶点

    min_dis = inf

    for j in range(node_num):

    if visited[j] == 0 and dis[j] < min_dis:

    min_dis = dis[j]

    # 把该顶点做为下次遍历的上一个顶点

    last_point = j

    # 最短顶点假加入 visited 数组

    visited[last_point] = 1

    # 对首次循环做特殊处理,不然在首次循环时会没法求出该点的上一个顶点

    if i == 0:

    parents[last_point] = start + 1

    for k in range(node_num):

    if G[last_point][k] < inf and dis[k] > dis[last_point] + G[last_point][k]:

    # 如果有更短的路径,更新 dis 和 记录 parents

    dis[k] = dis[last_point] + G[last_point][k]

    parents[k] = last_point + 1

    # 因为从 0 开始,最后把顶点都加 1

    return {key + 1: values for key, values in dis.items()}, {key + 1: values for key, values in parents.items()}

    if __name__ == '__main__':

    inf = float('inf')

    G = [[0, 1, 12, inf, inf, inf],

    [inf, 0, 9, 3, inf, inf],

    [inf, inf, 0, inf, 5, inf],

    [inf, inf, 4, 0, 13, 15],

    [inf, inf, inf, inf, 0, 4],

    [inf, inf, inf, inf, inf, 0]]

    dis, parents = Dijkstra(G, 1)

    print("dis: ", dis)

    print("parents: ", parents)

    输出为1

    2dis: {1: 0, 2: 1, 3: 8, 4: 4, 5: 13, 6: 17}

    parents: {1: -1, 2: 1, 3: 4, 4: 2, 5: 3, 6: 5}

    如果求 1 号顶点到 6 号顶点的最短距离,dis[6] = 17,所以最短距离为 17。

    再看 parents[6] = 5,说明 6 号顶点的上一个顶点为 5,parents[5] = 3,说明 5 号顶点的上一个顶点为 3,以此类推,最终 1 号顶点到 6 号顶点的路径为 1->2->4->3->5->6。

    优化思路其中每次找到离 1 号顶点最近的顶点的时间复杂度是 O(N),可以用“堆”来优化,使得这一部分的时间复杂度降低到 O(logN);

    另外对于边数 M 少于 N2 的稀疏图来说(把 M 远小于 N2 的图称为稀疏图,而 M 相对较大的图称为稠密图),可以用邻接表来代替邻接矩阵,使得整个时间复杂度优化到 O((M+N)logN)。注意,在最坏的情况下 M 就是 N2,这样的话 MlogN 要比 N2 还要大。但是大多数情况下并不会有那么多边,所以 (M+N)logN 要比 N2 小很多

    展开全文
  • 主要为大家详细介绍了python矩阵/字典实现最短路径算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法)。分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法——通过边实现松弛 # 指定一个点到其他各顶点的路径——单源最短路径 # 初始...
  • 主要介绍了Python实现的多叉树寻找最短路径算法,结合实例形式分析了Python使用深度优先查找获取多叉树最短路径相关操作技巧,需要的朋友可以参考下
  • 主要介绍了Python使用Dijkstra算法实现求解图中最短路径距离问题,简单描述了Dijkstra算法的原理并结合具体实例形式分析了Python使用Dijkstra算法实现求解图中最短路径距离的相关步骤与操作技巧,需要的朋友可以参考下
  • 最短路径算法 python

    万次阅读 2015-01-18 17:01:26
    算法研究上,最短路径是属于动态规划算法最短路径问题的具体内容 最短路径问题经常给出图结构,并选取起点和重点,根据这些已知条件找到从起点到终点的最短路径。 图中已知起点为A,终点为G,每条边的距离已

    最短路径

    最短路径问题在计算机和数学领域一直是一个经典问题,而且在其他领域有着广泛的应用:
    1.经济领域:社会网络分析
    2.运筹学领域
    3.机器人与人工智能
    4.通信网络
    在算法研究上,最短路径是属于动态规划算法。

    最短路径问题的具体内容

    最短路径问题经常给出图结构,并选取起点和重点,根据这些已知条件找到从起点到终点的最短路径。
    ../_images/graph.png
    图中已知起点为A,终点为G,每条边的距离已知,求A到G的最短距离。
    这个图很简单,很容易看出结果:
    A,C,F,G 长度为8
    A,D,F,G 长度为8

    抽象为数学问题后:
    假设J(v)表示从点v到下一点的最短距离。
    从终点G开始,依次回溯,J(G)=0,J(E)=4,J(F)=1,J(C)=3。。。结果如下:
    ../_images/graph2.png
    这一数学迭代过程可以表述为:
    1.从点A开始
    2.在任意点v上,选择下一个节点w时,使下式成立:
                            min{cost(v,w)+J(w)} for w in all nodes linked with node v

     解法

    图的数据结构:字典  Graph = dict()
    对于node A,Graph['A'] = [(node1,cost1),(node2,cost2),(note3,cost3),...]
    node1,node2,node3等都与node 'A'相连。当然,如果要自建数据类型Node,使用字典存储graph的数据结构时,一定要注意类型Node一定要hashable.即:
    class Node(object):
         '''
         '''
         def __hash__(self):
             return 'aNodeHashAlgorithm'.__hash__()

    1.初始化:


    M是一个比较大的数。

    2.迭代:

    (1).n=0

    (2).

    (3).如果J不再变化,就停止,否则,进行第(2)步。

    实例

    图文件:graph.txt
    问题为:找到node0到node99的最短路径。
    内容为:
    node0, node1 0.04, node8 11.11, node14 72.21
    node1, node46 1247.25, node6 20.59, node13 64.94
    node2, node66 54.18, node31 166.80, node45 1561.45
    node3, node20 133.65, node6 2.06, node11 42.43
    node4, node75 3706.67, node5 0.73, node7 1.02
    node5, node45 1382.97, node7 3.33, node11 34.54
    node6, node31 63.17, node9 0.72, node10 13.10
    node7, node50 478.14, node9 3.15, node10 5.85
    node8, node69 577.91, node11 7.45, node12 3.18
    node9, node70 2454.28, node13 4.42, node20 16.53
    node10, node89 5352.79, node12 1.87, node16 25.16
    node11, node94 4961.32, node18 37.55, node20 65.08
    node12, node84 3914.62, node24 34.32, node28 170.04
    node13, node60 2135.95, node38 236.33, node40 475.33
    node14, node67 1878.96, node16 2.70, node24 38.65
    node15, node91 3597.11, node17 1.01, node18 2.57
    node16, node36 392.92, node19 3.49, node38 278.71
    node17, node76 783.29, node22 24.78, node23 26.45
    node18, node91 3363.17, node23 16.23, node28 55.84
    node19, node26 20.09, node20 0.24, node28 70.54
    node20, node98 3523.33, node24 9.81, node33 145.80
    node21, node56 626.04, node28 36.65, node31 27.06
    node22, node72 1447.22, node39 136.32, node40 124.22
    node23, node52 336.73, node26 2.66, node33 22.37
    node24, node66 875.19, node26 1.80, node28 14.25
    node25, node70 1343.63, node32 36.58, node35 45.55
    node26, node47 135.78, node27 0.01, node42 122.00
    node27, node65 480.55, node35 48.10, node43 246.24
    node28, node82 2538.18, node34 21.79, node36 15.52
    node29, node64 635.52, node32 4.22, node33 12.61
    node30, node98 2616.03, node33 5.61, node35 13.95
    node31, node98 3350.98, node36 20.44, node44 125.88
    node32, node97 2613.92, node34 3.33, node35 1.46
    node33, node81 1854.73, node41 3.23, node47 111.54
    node34, node73 1075.38, node42 51.52, node48 129.45
    node35, node52 17.57, node41 2.09, node50 78.81
    node36, node71 1171.60, node54 101.08, node57 260.46
    node37, node75 269.97, node38 0.36, node46 80.49
    node38, node93 2767.85, node40 1.79, node42 8.78
    node39, node50 39.88, node40 0.95, node41 1.34
    node40, node75 548.68, node47 28.57, node54 53.46
    node41, node53 18.23, node46 0.28, node54 162.24
    node42, node59 141.86, node47 10.08, node72 437.49
    node43, node98 2984.83, node54 95.06, node60 116.23
    node44, node91 807.39, node46 1.56, node47 2.14
    node45, node58 79.93, node47 3.68, node49 15.51
    node46, node52 22.68, node57 27.50, node67 65.48
    node47, node50 2.82, node56 49.31, node61 172.64
    node48, node99 2564.12, node59 34.52, node60 66.44
    node49, node78 53.79, node50 0.51, node56 10.89
    node50, node85 251.76, node53 1.38, node55 20.10
    node51, node98 2110.67, node59 23.67, node60 73.79
    node52, node94 1471.80, node64 102.41, node66 123.03
    node53, node72 22.85, node56 4.33, node67 88.35
    node54, node88 967.59, node59 24.30, node73 238.61
    node55, node84 86.09, node57 2.13, node64 60.80
    node56, node76 197.03, node57 0.02, node61 11.06
    node57, node86 701.09, node58 0.46, node60 7.01
    node58, node83 556.70, node64 29.85, node65 34.32
    node59, node90 820.66, node60 0.72, node71 0.67
    node60, node76 48.03, node65 4.76, node67 1.63
    node61, node98 1057.59, node63 0.95, node64 4.88
    node62, node91 132.23, node64 2.94, node76 38.43
    node63, node66 4.43, node72 70.08, node75 56.34
    node64, node80 47.73, node65 0.30, node76 11.98
    node65, node94 594.93, node66 0.64, node73 33.23
    node66, node98 395.63, node68 2.66, node73 37.53
    node67, node82 153.53, node68 0.09, node70 0.98
    node68, node94 232.10, node70 3.35, node71 1.66
    node69, node99 247.80, node70 0.06, node73 8.99
    node70, node76 27.18, node72 1.50, node73 8.37
    node71, node89 104.50, node74 8.86, node91 284.64
    node72, node76 15.32, node84 102.77, node92 133.06
    node73, node83 52.22, node76 1.40, node90 243.00
    node74, node81 1.07, node76 0.52, node78 8.08
    node75, node92 68.53, node76 0.81, node77 1.19
    node76, node85 13.18, node77 0.45, node78 2.36
    node77, node80 8.94, node78 0.98, node86 64.32
    node78, node98 355.90, node81 2.59
    node79, node81 0.09, node85 1.45, node91 22.35
    node80, node92 121.87, node88 28.78, node98 264.34
    node81, node94 99.78, node89 39.52, node92 99.89
    node82, node91 47.44, node88 28.05, node93 11.99
    node83, node94 114.95, node86 8.75, node88 5.78
    node84, node89 19.14, node94 30.41, node98 121.05
    node85, node97 94.51, node87 2.66, node89 4.90
    node86, node97 85.09
    node87, node88 0.21, node91 11.14, node92 21.23
    node88, node93 1.31, node91 6.83, node98 6.12
    node89, node97 36.97, node99 82.12
    node90, node96 23.53, node94 10.47, node99 50.99
    node91, node97 22.17
    node92, node96 10.83, node97 11.24, node99 34.68
    node93, node94 0.19, node97 6.71, node99 32.77
    node94, node98 5.91, node96 2.03
    node95, node98 6.17, node99 0.27
    node96, node98 3.32, node97 0.43, node99 5.87
    node97, node98 0.30
    node98, node99 0.33
    node99, 
    文件格式为:第一个逗号前面为节点,第一个逗号后面为与这个节点相连的节点和节点间距离。
    首先要读入图文件。
    filename = 'graph.txt'
    def read_graph(filename):
        graph = {}
        with open(filename,'rb') as f:
            for line in f:
                info = line.split(',')
                print info
                key = info[0]
                key = key.strip()
                graph[key] = []
                if key != 'node99':
                    for ele in info[1:]:
                        node,cost = ele.split()
                        node = node.strip()
                        cost = cost.strip()
                        cost  = float(cost)
                        graph[key].append((node,cost))
        return graph
    然后,初始化J。
    J = {}    
    bigNum = 1e4
    for key in graph:   #初始化
        J[key] = bigNum
    J['node99'] = 0.0    #终点为零
    对J进行更新操作的函数。
    def updateJ(graph,J):
        newJ = {}
        
        for key in graph:
            if key == 'node99':
                newJ['node99'] = 0.0
            else:
                nodes = graph[key]
                newJ[key] = min(node[1]+J[node[0]] for node in nodes)
        return newJ
    经过多次迭代,直到J不再变化的时候。这个时候我们就可以直接把最短路径打印出来。
    def printPath(graph,J):
        start = 'node0'
        sum_cost = 0.0
        while start !='node99':
            print(start)
            running_min = 1e4
            for dest,cost in graph[start]:
                cost_of_path = cost + J[dest]
                if cost_of_path<running_min:
                    running_min = cost_of_path
                    min_cost = cost
                    min_dest = dest
            start = min_dest
            sum_cost += min_cost
        
        print('node99\n')
        print('total cost is {0:.2f}'.format(sum_cost))
    方法十分简单快捷。
    全部代码如下:
    # -*- coding: utf-8 -*-
    """
    Created on Sun Jan 18 17:18:32 2015
    
    @author: myjiayan
    """
    
    def read_graph(filename):
        graph = {}
        with open(filename,'rb') as f:
            for line in f:
                info = line.split(',')
                key = info[0]
                key = key.strip()
                graph[key] = []
                if key != 'node99':
                    for ele in info[1:]:
                        node,cost = ele.split()
                        node = node.strip()
                        cost = cost.strip()
                        cost  = float(cost)
                        graph[key].append((node,cost))
        return graph
    
    def updateJ(graph,J):
        newJ = {}
        
        for key in graph:
            if key == 'node99':
                newJ['node99'] = 0.0
            else:
                nodes = graph[key]
                newJ[key] = min(node[1]+J[node[0]] for node in nodes)
        return newJ
        
    def printPath(graph,J):
        start = 'node0'
        sum_cost = 0.0
        while start !='node99':
            print(start)
            running_min = 1e4
            for dest,cost in graph[start]:
                cost_of_path = cost + J[dest]
                if cost_of_path<running_min:
                    running_min = cost_of_path
                    min_cost = cost
                    min_dest = dest
            start = min_dest
            sum_cost += min_cost
        
        print('node99\n')
        print('total cost is {0:.2f}'.format(sum_cost))
        
                    
    if __name__ == '__main__':
        filename = r'C:\python-tutorial\graph.txt'
        J = {}
        graph = read_graph(filename)
        bigNum = 1e4
        for key in graph:
            J[key] = bigNum
        J['node99'] = 0.0 
        
        iterTimes = 0
        while True:
            newJ = updateJ(graph,J)
            iterTimes += 1
            if newJ == J:
                break
            else:
                J = newJ
        
        printPath(graph,J)
    结果就是:
    node0
    node8
    node11
    node18
    node23
    node33
    node41
    node53
    node56
    node57
    node60
    node67
    node70
    node73
    node76
    node85
    node87
    node88
    node93
    node94
    node96
    node97
    node98
    node99


    total cost is 160.55







    展开全文
  • 经过指定的中间节点集的最短路径算法Python源码,包括三种应用模式: 1、从起点过必经点到达终点; 2、从起点过必经点且不掉头到达终点; 3、有指定朝向点,从起点过必经点且不掉头到达终点。
  • python实现迪杰斯特拉算法,单源最短路径,有向图权值无负值,用邻接矩阵来存储有向图,实现路径存储和路径打印
  • 主要介绍了Python基于Floyd算法求解最短路径距离问题,结合完整实例形式详细分析了Python使用Floyd算法求解最短路径距离问题的相关操作技巧与注意事项,需要的朋友可以参考下
  • 主要介绍了python实现Dijkstra算法最短路径问题,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • 问题:使用某个顶点s作为输入参数,找出从s到所有其他顶点的最短路径。 说明:因为是无权图,因此我们可以为每台边赋值为1。这里选择v3为s作为起点。 问题分析 此时立刻可以说,从s到v3的最短路径是长为0的路径...

    本文参考来自数据结构与算法分析 java语言描述

    问题描述

    现有一个有向无权图。如下图所示:
    这里写图片描述
    问题:使用某个顶点s作为输入参数,找出从s到所有其他顶点的最短路径。
    说明:因为是无权图,因此我们可以为每台边赋值为1。这里选择v3为s作为起点。

    问题分析

    此时立刻可以说,从s到v3的最短路径是长为0的路径,标记此信息,得到下图。
    这里写图片描述
    现在开始寻找从s出发距离为1的顶点。这些顶点肯定是与s邻接的顶点,很明显,v1,v6从s出发只需要一条边就到了。所以,从s出发距离为1的顶点,为v1,v6。
    这里写图片描述
    现在开始寻找从s出发距离为2的顶点。这些顶点肯定是与v1,v6(距离为1的顶点)邻接的顶点。发现与v1邻接的顶点为v2,v4,与v6邻接的顶点没有(不能往回走,没有出边)。所以,从s出发距离为2的顶点,为v2,v4。
    这里写图片描述
    最后,考察与v2,v4邻接的顶点,即v5,v7。所以,从s出发距离为3的顶点,为v5,v7。
    这里写图片描述
    这种搜索图的方法称为广度优先搜索(breadth-first search)。按层处理顶点,距离起点近的顶点先处理,距离起点远的后处理。

    伪代码(处理节点)

    void unweighted(Vertex s){
        Queue<Vertex> q = new Queue<Vertex>();
        //把每个顶点的距离设为无穷大
        for each Vertex v
            v.dist = INFINITY
        //将起点的距离设为0
        s.dist = 0;
        //起点入队,作为算法的开始
        q.enqueue(s);
        //只要队列不为空,便继续循环
        while( !q.isEmpty() ){
            //获得出队顶点
            Vertex v = q.dequeue();
            //对与v邻接的每个顶点进行处理
            for each Vertex w adjacent to v
                if(w.dist == INFINITY){
                    w.dist = v.dist + 1;
                    w.path = v;//代表w的上一个经过的顶点为v
                    //完成操作后,便入队,以用来接着分析与w邻接的顶点们
                    q.enqueue( w );
                }
        }
    }

    实现过程

    这里写图片描述
    这里写图片描述
    从s开始到顶点的距离放到dv列里,pv列用来代表,当前行代表的顶点的上一个经过的顶点。known列代表此顶点已经被处理过了。
    初始化时,将起点的距离设置为0,且所有的顶点都不是know的。
    这里写图片描述
    结合伪代码进行分析:
    【1】当第一次循环中,出队的是v3(每次循环只出队一个顶点)
    【2】而第一次循环结束时,就是上表中“v3出队后”的数据情况,如下
    【3】此时,对v3的邻接的顶点们都作了处理,所以v3就从F变成了T(即已知)
    【4】与v3邻接的顶点v1,v6都作了处理,dv都变成了1,pv都为v3
    【5】而因为与v1,v6的邻接顶点都还没有开始处理呢,所以v1,v6的F还不能变成T

    得到无权最短路径

    通过观察图,可以发现有两条路径长为3的最短路径。
    【1】v3 => v1 => v2 => v5
    【2】v3 => v1 => v4 => v7
    我们可以通过数据变化表的最终情况来找到这两条路径。
    这里写图片描述
    注意,第一行代表v1,以此类推。
    以找到v3 => v1 => v2 => v5路径为例,过程如下:
    【1】找到距离为0的顶点,0在且只在第三行,所以第一个顶点为v3
    【2】找到距离为1且pv为v3的顶点,有第一行和第六行,这里必须选一个,这里选第一行,所以第二个顶点为v1
    【3】找到距离为2且pv为v1的顶点,有第二行和第四行,这里选第二行,所以第三个顶点为v2
    【4】找到距离为3且pv为v2的顶点,只有第五行,所以第四个顶点为v5
    【5】找到距离为4且pv为v5的顶点,没有,结束。
    其实,以上步骤,是给出了,在对顶点进行数据处理后,找出无权最短路径的算法的思想。
    其实可以,维护一些顶点间指针,用来指向下一个顶点,这样就可以用递归的思路来做,从起点开始,每递归到下一层距离dv便加1,用一个中间变量存储经过的顶点,每调用一次递归,便打印这个中间变量,这样,便能得到所有的无权最短路径。
    这里得到无权最短路径的伪代码也不给出了,以上分析供大家理解参考。

    代码实现

    纸上得来终觉浅,绝知此事要躬行!还是觉得用代码实现一遍比较好。

    from queue import Queue
    class Vertex:
        #顶点类
        def __init__(self,vid,outList):
            self.vid = vid#出边
            self.outList = outList#出边指向的顶点id的列表,也可以理解为邻接表
            self.know = False#默认为假
            self.dist = float('inf')#s到该点的距离,默认为无穷大
            self.prev = 0#上一个顶点的id,默认为0
    
    #创建顶点对象
    v1=Vertex(1,[2,4])
    v2=Vertex(2,[4,5])
    v3=Vertex(3,[1,6])
    v4=Vertex(4,[3,5,6,7])
    v5=Vertex(5,[7])
    v6=Vertex(6,[])
    v7=Vertex(7,[6])
    #创建一个长度为8的数组,来存储顶点,0索引元素不存
    vlist = [False,v1,v2,v3,v4,v5,v6,v7]
    def unweighted():
        #起点为v3
        vlist[3].dist = 0
        q = Queue()
        q.put(vlist[3])
        while(not q.empty()):
            v = q.get()#返回并删除队列头部元素
            for w in v.outList:
                if(vlist[w].dist == float('inf')):
                    vlist[w].dist = v.dist + 1
                    vlist[w].prev = v.vid
                    q.put(vlist[w])
    
    unweighted()
    print('v1.prev:',v1.prev,'v1.dist',v1.dist)
    print('v2.prev:',v2.prev,'v2.dist',v2.dist)
    print('v3.prev:',v3.prev,'v3.dist',v3.dist)
    print('v4.prev:',v4.prev,'v4.dist',v4.dist)
    print('v5.prev:',v5.prev,'v5.dist',v5.dist)
    print('v6.prev:',v6.prev,'v6.dist',v6.dist)
    print('v7.prev:',v7.prev,'v7.dist',v7.dist)
    

    运行结果:
    这里写图片描述
    与数据变化表的最终情况一致。
    这里你可能会问,Vertex类的init函数中,明明有know成员,为什么在程序没有使用know成员(在处理节点后,就把该节点的know置为Ture),因为if(vlist[w].dist == float('inf'))的判断就相当于判断节点的know是否为Ture,因为一个已知的节点,它的距离就肯定不是无穷大了。
    然后再使用递归,打印出所有可能的最短路径,把以下代码和以上代码合在一起就可以了。

    traj_list = [3]#v3是起点直接加上
    
    def print_traj(dist):
        last = traj_list[-1]
        print(traj_list,'该路径的长度为:',vlist[last].dist)
        temp_list = []#存储下一步的选项
        for i in range(1,len(vlist)):
            v = vlist[i]
            if((v.dist==dist) and (v.prev==last)):
                temp_list.append(i)
        if(len(temp_list)==0):
            return#终点
        #递归每个选项
        for i in temp_list:#i为顶点的索引
            traj_list.append(i)
            print_traj(dist+1)
            traj_list.pop()
    
    
    print_traj(1)

    这里写图片描述

    展开全文
  • Python小白的数学建模课-16.最短路径算法

    千次阅读 多人点赞 2021-07-07 19:34:29
    最短路径问题是图论研究中的经典算法问题,用于计算图中一个顶点到另一个顶点的最短路径。 求最短路径长度的常用算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法,另外还有启发式算法 A\*。 『Python小白的...

    • 最短路径问题是图论研究中的经典算法问题,用于计算图中一个顶点到另一个顶点的最短路径。
    • 在图论中,最短路径长度与最短路径距离却是不同的概念和问题,经常会被混淆。
    • 求最短路径长度的常用算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法,另外还有启发式算法 A*。
    • 『Python小白的数学建模课 @ Youcans』带你从数模小白成为国赛达人。


    1. 最短路径问题

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

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

    1.1 最短路径长度与最短路径距离

    在日常生活中,最短路径长度与最短路径距离好像并没什么区别。但在图论中最短路径长度与最短路径距离却是不同的概念和问题,经常会被混淆。

    图论中有无权图和有权图,无权图中的边没有权,赋权图的边带有权,可以表示距离、时间、费用或其它指标。在问题文字描述中,往往并不直接指出是无权图还是有权图,这时就要特别注意最短路径与最短加权路径的区别。

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

    通俗地说,路径长度可以认为是飞行棋的步数,或者公交站点的站数,相邻顶点之间为一步,相隔几个顶点就是几站。路径长度是从路径起点到终点的步数,计算最短路径是要计算从起点到终点步数最少的路径。

    如果问题不涉及相邻顶点间的距离,要计算从起点到终点的最短路径及对应的最短路径长度,是指这条路径从起点到终点有几步(站),在图论中称为最短路径长度。但是,如果问题给出相邻顶点之间的道路长度或距离,姑且称为各路段的距离,要计算从起点到终点的最短路径及对应的最短距离,显然并不是要找经过最少步数的路径,而是在找路径中各路段的距离之和最小的路径,在图论中称为最短加权路径长度——这里权重是路段距离。

    相邻顶点的连接边的权,不仅可以是路段距离,也可以是时间、费用等指标。问题就变成寻求最短时间、最低成本的路径,这实际上也是最短加权路径长度问题。


    1.2 最短路径的常用算法

    求解最短路径长度的常用算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法,另外还有启发式算法 A*。

    1.2.1 Dijkstra 算法

    Dijkstra 算法是经典的最短路径算法,在数据结构、图论、运筹学中都是教学的基本算法。有趣的是,在数据结构中 Dijkstra 算法通常是按贪心法讲述,而在运筹学中则被认为是动态规划法。

    Dijkstra算法从起点开始,采用贪心法策略,每次遍历距离起点最近且未访问过的邻接顶点, 层层扩展直到终点为止。

    Dijkstra算法可以求出加权最短路径的最优解,算法的时间复杂度为 O(n^2)。如果边数远小于 n^2,可以用堆结构将复杂度降为O((m+n)log(n))。

    Dijkstar算法不能处理负权边,这是由于贪心法的选择规则决定的。

    1.2.2 Bellman-Ford 算法

    Bellman-Ford 算法是求含负权图的单源最短路径算法。算法原理是对图进行 V-1次松弛操作,得到所有可能的最短路径。

    Bellman-Ford 算法可以处理负权边。其基本操作“拓展”是在深度上搜索,而“松弛”操作则在广度上搜索,因此可以对负权边进行操作而不影响结果。

    Bellman-Ford 算法的效率很低,时间复杂度高达 O(V*E),V、E 分别是顶点和边的数量。SPFA 是 Bellman-Ford 的队列优化,通过维护一个队列极大地减少了重复计算,时间复杂度为 O(k*E) 。

    Dijkstra 算法在求解过程中,起点到各顶点的最短路径求出后就不变了。Bellman算法在求解过程中,每次循环都要修改所有顶点间的距离,起点到各顶点最短路径一直要到算法结束才确定。

    1.2.3 Floyd 算法

    Floyd 算法又称插点法,运用动态规划思想求解有权图中多源点之间最短路径问题。算法从图的带权邻接矩阵开始,递归地进行 n 次更新得到图的距离矩阵,进而可以得到最短路径节点矩阵。

    Floyd 算法的时间复杂度为 O(n^3),空间复杂度为 O(n^2)。算法时间复杂度较高,不适合计算大量数据。Floyd 算法的优点是可以一次性求解任意两个节点之间的最短距离,对于稠密图的效率高于执行 V 次 Dijkstra算法。

    Floyd 算法可以处理负权边。

    Floyd 算法号称只有 5行代码,我们来欣赏一下:

    for(k=0;k<n;k++)//中转站0~k
        for(i=0;i<n;i++) //i为起点
            for(j=0;j<n;j++) //j为终点
                if(d[i][j]>d[i][k]+d[k][j])//松弛操作 
                    d[i][j]=d[i][k]+d[k][j]; 
    

    1.2.4 A* 算法

    A*算法是一种静态路网中求解最短路径最有效的直接搜索方法。

    A*算法是启发式算法,采用最佳优先(Best-first)搜索策略,基于估价函数对每个搜索位置的评估结果,猜测最好的位置优先进行搜索。

    A*算法极大地减少了低质量的搜索路径,因而搜索效率很高,比传统的路径规划算法实时性更高、灵活性更强;但是,A*算法找到的是相对最优路径,不是绝对的最短路径,适合大规模、实时性高的问题。

    1.3 最短路径算法的选择

    1. 需要求解任意两个节点之间的最短距离,使用 Floyd 算法;
    2. 只要求解单源最短路径问题,有负权边时使用 Bellman-Ford 算法,没有负权边时使用 Dijkstra 算法;
    3. A*算法找到的是相对最优路径,适合大规模、实时性高的问题。


    2. NetworkX 中的最短路径算法

    NetworkX 提供了丰富的最短路径函数,除了常见的 Dijkstra 算法、Bellman-ford 算法、Floyd Warshall 算法和 A*算法,还有 Goldbery-Radzik 算法和 Johnson 算法。其中,Bellman-ford 算法函数使用的是队列改进算法,即以 SPFA 算法实现。

    2.1 无向图和有向图的最短路径求解函数

    函数功能
    shortest_path(G[, source, target, weight,…])计算图中的最短路径
    all_shortest_paths(G, source, target[,…])计算图中所有最短的简单路径
    shortest_path_length(G[, source, target, …])计算图中的最短路径长度
    average_shortest_path_length(G[, weight, method])计算平均最短路径长度

    其中,最基本的求解最短路径函数 shortest() 和 最短路径长度 shortest_path_length() 是 ‘dijkstra’ 算法和 ‘bellman-ford’ 算法的集成接口,可以通过 method=‘dijkstra’ 选择不同的算法。

    shortest_path(G, source=None, target=None, weight=None, method=‘dijkstra’)
    shortest_path_length(G, source=None, target=None, weight=None, method=‘dijkstra’)

    主要参数:

    • G(NetworkX graph):图。
    • source (node):起点。
    • target (node):终点。
    • weight (string or function):参数为字符串(string)时,按该字符串查找边的属性作为权重;如果该字符串对应的边属性不存在,则权重置为 1;参数为函数时,边的权重是函数的返回值。
    • method [string, optional (default = ‘dijkstra’)]:支持的选项为 ‘dijkstra’, ‘bellman-ford’。

    2.2 无权图最短路径算法

    函数功能
    single_source_shortest_path(G, source[,cutoff])计算从源到所有可达节点的最短路径
    single_source_shortest_path_length(G,source)计算从源到所有可达节点的最短路径长度
    single_target_shortest_path(G, target[,cutoff])计算从所有可达节点到目标的最短路径
    single_target_shortest_path_length(G,target)计算从所有可达节点到目标的最短路径长度
    all_pairs_shortest_path(G[, cutoff])计算所有节点之间的最短路径
    all_pairs_shortest_path_length(G[, cutoff])计算所有节点之间的最短路径长度

    2.3 有权图最短路径算法

    函数功能
    dijkstra_path(G, source, target[, weight])计算从源到目标的最短加权路径
    dijkstra_path_length(G, source, target[,weight])计算从源到目标的最短加权路径长度
    all_pairs_dijkstra_path(G[, cutoff, weight])计算所有节点之间的最短加权路径
    all_pairs_dijkstra_path_length(G[, cutoff,… ])计算所有节点之间的最短加权路径长度
    bellman_ford_path(G, source, target[, weight])计算从源到目标的最短路径
    bellman_ford_path_length(G, source, target)计算从源到目标的最短路径长度
    all_pairs_bellman_ford_path(G[, weight])计算所有节点之间的最短路径
    all_pairs_bellman_ford_path_length(G[,weight])计算所有节点之间的最短路径长度
    floyd_warshall(G[, weight])用 Floyd 法计算所有节点之间的最短路径长度
    floyd_warshall_numpy(G[, nodelist, weight])用 Floyd 法计算所有指定节点之间的最短路径长度


    3. NetworkX 中的 Dijkstra 算法

    NetworkX 中关于 Dijkstra 算法提供了 13 个函数,很多函数的功能是重复的。这里只介绍最基本的函数 dijkstra_path() 和 dijkstra_path_length()。

    3.1 dijkstra_path() 和 dijkstra_path_length() 使用说明

    dijkstra_path() 用于计算从源到目标的最短加权路径,dijkstra_path_length() 用于计算从源到目标的最短加权路径长度。

    dijkstra_path(G, source, target, weight=‘weight’)
    dijkstra_path_length(G, source, target, weight=‘weight’)

    主要参数:

    • G(NetworkX graph):图。
    • source (node):起点。
    • target (node):终点。
    • weight (string or function):参数为字符串(string)时,按该字符串查找边的属性作为权重;如果该字符串对应的边属性不存在,则权重置为1;参数为函数时,边的权重是函数的返回值。

    返回值:

    • dijkstra_path() 的返回值是最短加权路径中的节点列表,数据类型为list。
    • dijkstra_path_length() 的返回值是最短加权路径的长度(路径中的边的权重之和)。

    3.2 例题 1:无向图的最短路径问题

    例题 1:已知如图的有权无向图,求顶点 v1 到 顶点 v11 的最短路径。

    本问题来自:司守奎、孙兆亮,数学建模算法与应用(第2版),P43,例4.3,国防工业出版社。

    在这里插入图片描述

    程序说明:

    1. 图的输入。本例的问题是稀疏的有权无向图,使用 add_weighted_edges_from() 函数可以用列表形式向图中添加多条赋权边,每个赋权边以元组 (node1,node2,weight) 表示。
    2. 图的绘制。使用 nx.draw() 绘图时,默认的顶点位置可能并不理想,可以通过 pos 指定顶点位置。
    3. 绘制边的属性。使用 nx.draw_networkx_edge_labels() 可以绘制边的属性,例程中选择显示权重属性。
    4. 使用 dijkstra_path() 和 dijkstra_path_length() 求指定顶点之间的最短加权路径和最短加权路径长度。

    3.3 dijkstra_path() 算法例程

    # mathmodel16_v1.py
    # Demo16 of mathematical modeling algorithm
    # Demo of shortest path with NetworkX
    # Copyright 2021 YouCans, XUPT
    # Crated:2021-07-07
    
    import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
    import networkx as nx  # 导入 NetworkX 工具包
    
    # 问题 1:无向图的最短路问题(司守奎,数学建模算法与应用,P43,例4.3)
    G1 = nx.Graph()  # 创建:空的 无向图
    G1.add_weighted_edges_from([(1,2,2),(1,3,8),(1,4,1),
                                (2,3,6),(2,5,1),
                                (3,4,7),(3,5,5),(3,6,1),(3,7,2),
                                (4,7,9),
                                (5,6,3),(5,8,2),(5,9,9),
                                (6,7,4),(6,9,6),
                                (7,9,3),(7,10,1),
                                (8,9,7),(8,11,9),
                                (9,10,1),(9,11,2),
                                (10,11,4)])  # 向图中添加多条赋权边: (node1,node2,weight)
    print('nx.info:',G1.nodes)  # 返回图的基本信息
    
    # 两个指定顶点之间的最短加权路径
    minWPath_v1_v11 = nx.dijkstra_path(G1, source=1, target=11)  # 顶点 1 到 顶点 11 的最短加权路径
    print("顶点 v1 到 顶点 v11 的最短加权路径: ", minWPath_v1_v11)
    # 两个指定顶点之间的最短加权路径的长度
    lMinWPath_v1_v11 = nx.dijkstra_path_length(G1, source=1, target=11)  # 最短加权路径长度
    print("顶点 v1 到 顶点 v11 的最短加权路径长度: ", lMinWPath_v1_v11)
    
    pos = {1: (0,4), 2: (5,7), 3: (5,4), 4: (5,1), 5: (10,7), 6: (10,4), 7: (10,1),
           8: (15,7), 9: (15,4), 10: (15,1), 11: (20,4)}  # 指定顶点位置
    labels = nx.get_edge_attributes(G1, 'weight')  # 设置边的 labels 为 ‘weight'
    nx.draw(G1, pos, with_labels=True, font_color='w')  # 绘制无向图
    nx.draw_networkx_edge_labels(G1, pos, edge_labels=labels, font_color='c')  # 显示边的权值
    plt.show()
    

    3.4 程序运行结果

    nx.info: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
    顶点 v1 到 顶点 v11 的最短加权路径:  [1, 2, 5, 6, 3, 7, 10, 9, 11]
    顶点 v1 到 顶点 v11 的最短加权路径长度:  13
    


    4. NetworkX 中的 Bellman-Ford 算法

    NetworkX 中关于 Bellman-Ford 算法提供了多个函数,这里只介绍最基本的函数 bellman_ford_path() 和 bellman_ford_path_length()。

    4.1 bellman_ford_path() 和 bellman_ford_path_length() 使用说明

    bellman_ford_path() 用于计算从源到目标的最短加权路径,bellman_ford_path_length() 用于计算从源到目标的最短加权路径长度。

    bellman_ford_path(G, source, target, weight=‘weight’)
    bellman_ford_path_length(G, source, target, weight=‘weight’)

    主要参数:

    • G(NetworkX graph):图。
    • source (node):起点。
    • target (node):终点。
    • weight (string):按字符串查找边的属性作为权重。默认值为权重 ‘weight’。

    返回值:

    • bellman_ford_path() 的返回值是最短加权路径中的节点列表,数据类型为list。
    • bellman_ford_path_length() 的返回值是最短加权路径的长度(路径中的边的权重之和)。

    4.2 例题 2:城市间机票价格问题

    例题 2:城市间机票价格问题。

    已知 6个城市之间的机票票价如矩阵所示(无穷大表示没有直航),求城市 c0 到其它城市 c1…c5 的票价最便宜的路径及票价。

    [ 0 50 ∞ 40 25 10 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 55 10 25 ∞ 25 55 0 ] \begin{bmatrix} 0 & 50 & \infty & 40 & 25 & 10\\ 50 & 0 & 15 & 20 & \infty & 25\\ \infty & 15 & 0 & 10 & 20 & \infty\\ 40 & 20 & 10 & 0 & 10 & 25\\ 25 & \infty & 20 & 10 & 0 & 55\\ 10 & 25 & \infty & 25 & 55 & 0\\ \end{bmatrix} 050402510500152025150102040201001025252010055102525550
    本案例问题改编自:司守奎、孙兆亮,数学建模算法与应用(第2版),P41,例4.1,国防工业出版社。

    程序说明

    1. 图的输入。使用 pandas 中 DataFrame 读取数据文件非常方便,本例中以 pandas 输入顶点邻接矩阵,使用 nx.from_pandas_adjacency(dfAdj) 转换为 NetworkX 的图。
    2. 邻接矩阵。邻接矩阵 dfAdj (i,j) 的值表示连接顶点 i、j 的边的权值, dfAdj (i,j) = 0 表示 i、j 不相邻, 本例中表示没有直航。
    3. 最短路径与最短路径长度。nx.shortest_path() 返回最短路径。nx.shortest_path_length() 返回最短路径长度,本例中可以理解为从起点到终点的乘机次数:1 表示直航,2 表示中转一次。
    4. 最短加权路径长度。nx.bellman_ford_path_length() 返回最短加权路径长度,本例中权重为票价,最短加权路径长度即为两点间最便宜的直航或中转的机票票价。
      通过本案例,可以直观地理解最短路径长度与最短加权路径长度的区别。

    4.3 bellman_ford_path() 算法例程

    # mathmodel16_v1.py
    # Demo16 of mathematical modeling algorithm
    # Demo of shortest path with NetworkX
    # Copyright 2021 YouCans, XUPT
    # Crated:2021-07-07
    
    import pandas as pd
    import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
    import networkx as nx  # 导入 NetworkX 工具包
    
    # 问题 2:城市间机票价格问题(司守奎,数学建模算法与应用,P41,例4.1)
    # # 从Pandas数据格式(顶点邻接矩阵)创建 NetworkX 图
    # # from_pandas_adjacency(df, create_using=None) # 邻接矩阵,n行*n列,矩阵数据表示权重
    dfAdj = pd.DataFrame([[0, 50, 0, 40, 25, 10],  # 0 表示不邻接,
                          [50, 0, 15, 20, 0, 25],
                          [0, 15, 0, 10, 20, 0],
                          [40, 20, 10, 0, 10, 25],
                          [25, 0, 20, 10, 0 ,55],
                          [10, 25, 0, 25, 55, 0]])
    G2 = nx.from_pandas_adjacency(dfAdj)  # 由 pandas 顶点邻接矩阵 创建 NetworkX 图
    
    # 计算最短路径:注意最短路径与最短加权路径的不同
    # 两个指定顶点之间的最短路径
    minPath03 = nx.shortest_path(G2, source=0, target=3)  # 顶点 0 到 顶点 3 的最短路径
    lMinPath03 = nx.shortest_path_length(G2, source=0, target=3)  #最短路径长度
    print("顶点 0 到 3 的最短路径为:{},最短路径长度为:{}".format(minPath03, lMinPath03))
    # 两个指定顶点之间的最短加权路径
    minWPath03 = nx.bellman_ford_path(G2, source=0, target=3)  # 顶点 0 到 顶点 3 的最短加权路径
    # 两个指定顶点之间的最短加权路径的长度
    lMinWPath03 = nx.bellman_ford_path_length(G2, source=0, target=3)  #最短加权路径长度
    print("顶点 0 到 3 的最短加权路径为:{},最短加权路径长度为:{}".format(minWPath03, lMinWPath03))
    
    for i in range(1,6):
        minWPath0 = nx.bellman_ford_path(G2, source=0, target=i)  # 顶点 0 到其它顶点的最短加权路径
        lMinPath0 = nx.bellman_ford_path_length(G2, source=0, target=i)  #最短加权路径长度
        print("城市 0 到 城市 {} 机票票价最低的路线为: {},票价总和为:{}".format(i, minWPath0, lMinPath0))
    
    nx.draw_shell(G2, with_labels=True, node_color='r', edge_color='b', font_color='w', width=2)
    plt.show()
    

    4.4 程序运行结果

    顶点 03 的最短路径为:[0, 3],最短路径长度为:1
    顶点 03 的最短加权路径为:[0, 4, 3],最短加权路径长度为:35
    城市 0 到 城市 1 机票票价最低的路线为: [0, 5, 1],票价总和为:35
    城市 0 到 城市 2 机票票价最低的路线为: [0, 4, 2],票价总和为:45
    城市 0 到 城市 3 机票票价最低的路线为: [0, 5, 3],票价总和为:35
    城市 0 到 城市 4 机票票价最低的路线为: [0, 4],票价总和为:25
    城市 0 到 城市 5 机票票价最低的路线为: [0, 5],票价总和为:10
    

    在这里插入图片描述


    5. 总结

    1. 最短路径问题是图论研究中的经典算法问题,用于计算图中一个顶点到另一个顶点的最短路径。
    2. 在图论中,求最短路径长度是要计算从起点到终点步数最少的路径,而求最短路径距离是要计算最短加权路径长度。从例 2的运行结果可以对比二者的区别。
    3. 求最短路径长度的常用算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法,另外还有启发式算法 A*。
    4. 对于稀疏的图推荐使用列表形式添加赋权边,对于稠密图、完全图建议使用 DtaFrame 读取数据文件后再转换为 NetworkX 格式。

    【本节完】



    版权声明:

    欢迎关注『Python小白的数学建模课 @ Youcans』 原创作品

    原创作品,转载必须标注原文链接:(https://blog.csdn.net/youcans/article/details/118555468)。

    Copyright 2021 Youcans, XUPT

    Crated:2021-07-07


    欢迎关注 『Python小白的数学建模课 @ Youcans』 系列,持续更新
    Python小白的数学建模课-01.新手必读
    Python小白的数学建模课-02.数据导入
    Python小白的数学建模课-03.线性规划
    Python小白的数学建模课-04.整数规划
    Python小白的数学建模课-05.0-1规划
    Python小白的数学建模课-06.固定费用问题
    Python小白的数学建模课-07.选址问题
    Python小白的数学建模课-09.微分方程模型
    Python小白的数学建模课-10.微分方程边值问题
    Python小白的数学建模课-12.非线性规划
    Python小白的数学建模课-15.图论的基本概念
    Python小白的数学建模课-16.最短路径算法
    Python小白的数学建模课-17.条件最短路径算法
    Python小白的数学建模课-18.最小生成树问题
    Python小白的数学建模课-19.网络流优化问题
    Python小白的数学建模课-20.网络流优化案例
    Python小白的数学建模课-21.关键路径法
    Python小白的数学建模课-A1.国赛赛题类型分析
    Python小白的数学建模课-21.关键路径法
    Python小白的数学建模课-22.插值方法
    Python小白的数学建模课-A1.国赛赛题类型分析
    Python小白的数学建模课-A2.2021年数维杯C题探讨
    Python小白的数学建模课-A3.12个新冠疫情数模竞赛赛题及短评
    Python小白的数学建模课-B2. 新冠疫情 SI模型
    Python小白的数学建模课-B3. 新冠疫情 SIS模型
    Python小白的数学建模课-B4. 新冠疫情 SIR模型
    Python小白的数学建模课-B5. 新冠疫情 SEIR模型
    Python小白的数学建模课-B6. 新冠疫情 SEIR改进模型


    展开全文
  • Dijkstra算法类似于贪心算法计算从起点到指定顶点的最短路径,通过不断选择距离起点最近的顶点,来逐渐扩大最短路径权值,直到覆盖图中所有顶点(与方法4不同,其对边的松弛顺序是随意进行的)。其应用根本在于最短...
  • 得到无权最短路径 代码实现 问题描述 现有一个有向无权图。如下图所示: 问题:使用某个顶点s作为输入参数,找出从s到所有其他顶点的最短路径。 说明:因为是无权图,因此我们可以为每台边赋值为1。这里选择...
  • |-图的表示 邻接矩阵:适合表示稠密图(完全图) 邻接表:适合表示稀疏图|-图的遍历 深度优先遍历 可以用于计算图的连通分量个数 寻路: 定义一个from数组指向该点的前一个...O(n^2) 广度优先遍历 最短路径 复...
  • 在本篇内容里小编给大家整理的是关于python实现最短路径的实例方法,有需要的朋友们可以参考下。
  • 最短路径python

    2020-11-29 17:22:44
    最短路径问题(python实现)解决最短路径问题:(如下三种算法)(1)迪杰斯特拉算法(dijkstra算法)(2)弗洛伊德算法(floyd算法) (3)spfa算法第一种算法:dijkstra算法广度优先搜索解决赋权有向图或者无向图...
  • python实现 最短路径算法

    万次阅读 2019-03-11 09:40:14
    Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。通常可以在任何图中使用,包括有向图、带负权边的图。 存储方式采用邻接矩阵 2.示例 0 1 2 6 3 1 0 3 5 2 2 3 0 ...
  • 以下代码所针对的有向加权图参照我的另一篇博客Dijkstra最短路径算法——java代码实现 import numpy as np class Dijkstra: def __init__(self, index, distance, flag, transfer, v, e, dis): self.index = ...
  • Python算法实现 -- K最短路径算法

    千次阅读 2020-06-15 15:11:30
    实现在一张图中寻找K条最短路径(较短路径)以及代码测试过程中学习到的Python基础知识。
  • B站:dijkstra算法最短路径 看过之后就知道基本原理了。 算法实现步骤: ① 每次找出当前图中距离源点1最近的点k, ② 计算源点1经过该点k到达某个点j是否比原来更近,如果更近,则把源点1到某个点j的距离,替换为...
  • 主要为大家详细介绍了python广度优先搜索得到两点间最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,718
精华内容 4,687
关键字:

最短路径算法python

python 订阅