用图讲解狄克斯特拉（DiskStra）算法，python实现。

逃离我推掉我的手 2023-01-03 04:17 186阅读 0赞

## 最短路径 ##

在一个带权图中，顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径最短的那条路径称为最短路径。  
如图所示，求双子峰到金门大桥的最短距离。  
![20210107104713741.png_pic_center][]

此类问题要用到狄克斯特拉（DiskStra）算法

## 使用狄克斯特拉（DiskStra）算法 ##

![20210107105154741.png_pic_center][] 图中每个数字都是时间，为此找出从起点到终点用时最短的路径。

如果你使用广度优先搜索，[广度优先搜索算法BFS讲解以及python 实现][BFS_python]  
你将得到下面这条段数最少的路径。  
![20210107105438851.png_pic_center][]

这条路径耗费7分钟，我们接下来找找还有没有更短的路径。  
狄克斯特拉（DiskStra）算法 包含4个步骤：

1.  找出可在最短时间内到达的点
2.  更新该节点的邻居的开销
3.  重复计算该过程，直到对所有节点都做了
4.  计算最终路径

第一步：你站在起点，可以走的点是A，B。到达A需要6分钟，到达B需要2分钟，其他节点不能到达，设为无穷。

![20210107125941706.png_pic_center][]

第二步：因为起点到B最近，然后计算B前往各邻居的距离  
B到A的距离是3，我们找到一条前往A点的更短路径5，从起点直接前往A点距离是6，则更新库中起点到A的距离。  
![20210107130214244.png_pic_center][]

对于节点B的邻居，如果找到前往它的更短路径，就更新其开销，在这里我们找到了：前往A点的更短路径，时间由6分钟缩短到了5分钟；前往终点的更短路径，时间由无穷大缩短到7分钟。  
![20210107130655480.png_pic_center][]

第三步：重复  
重复第一步,找出最短时间可以到达的点，前面对节点B执行了第二步，除B点外，还有节点A  
![20210107130909689.png_pic_center][]

重读第二步，更新节点A所有邻居的开销  
![20210107131007381.png_pic_center][]

你发现前往终点的时间为6分钟。

对每个节点都应用狄克斯特拉（DiskStra）算法，现在知道前往B节点2分钟，A分钟，终点6分钟。

狄克斯特拉（DiskStra）算法适用于有向无环图。

## 算例1实现 ##

以图为例  
![20210107132756947.png_pic_center][]

**第一步：解决这个问题，需要准备三个散列表**  
![20210107135115447.png_pic_center][]  
第一个散列表表示图，依次是父节点，子节点，权重。第一个散列表图可以用散列表嵌套表示。

""" 、、、、、、 第一个散列表 用于表示图 、、、、、、 """
    graph={ }
    #起点 到各邻居的关系
    graph["start"]={ }
    graph["start"]["a"]=6
    graph["start"]["b"]=2
    #print(graph["start"].keys())#dict_keys(['a', 'b'])
    #节点a到各邻居关系
    graph["a"]={ }
    graph["a"]["fin"]=1
    
    #节点b到各邻居关系
    graph["b"]={ }
    graph["b"]["a"]=3
    graph["b"]["fin"]=5
    
    #终点与各邻居关系
    graph["fin"]={ }#终点没有邻居

第二个散列表为初始时起点出发到各节点的距离，随着算法进行需要不断更新。

""" 第二个散列表 节点的开销。节点的开销表示起点出发到该节点需要多少时间"""
    infinity=float("inf")#无穷大
    costs={ }
    costs['a']=6
    costs['b']=2
    costs['fin']=infinity

第三个散列表。左边为子节点，右边为父节点，用来表示路径。随着算法进行需要不断更新，是针对出发点建立的

""" 第三个散列表 存储 路径 . parents['a']="start"表示节点a的上一节点是start,如果后面发现更短路径，可以修改为parents['a']=b"""
    parents={ }
    parents['a']="start"
    parents['b']="start"
    parents['fin']=None#出发点不能直接到达

**第二步：需要一个数组，存储已经处理过的节点**

""" 需要一个数组，存储已经处理过的节点 """
    processed=[]

**第三步：最小开销节点函数**

""" 开销最小的函数 """
    def find_lowest_cost_node(costs):
        lowest_cost=float('inf')
        lowest_cost_node=None
        for node in costs:#遍历每个节点
            cost=costs[node]
            if cost<lowest_cost and node not in processed:#如果当前节点小于最小开销，且没有处理过
                lowest_cost_node=node #则将该节点设为最小开销节点
                lowest_cost=cost#更新最小开销
        return lowest_cost_node

**第四步：DiskStra算法**  
![20210107144301298.png_pic_center][]

""" DiskStra算法"""
    node=find_lowest_cost_node(costs) #在未处理的节点中找到开销最小的节点，即离出发点最近的点
    while node  is not None: #这个循环表示所有节点处理过才会结束
        cost=costs[node]
        neighbors=graph[node]
        for n in neighbors.keys():#遍历当前节点的所有邻居
            new_cost=cost+neighbors[n]
            if costs[n]>new_cost:#如果经当前节点离该邻居更近
                costs[n]=new_cost#就更新该节点的开销
                parents[n]=node #同时将该邻居的父节点设置为该节点
        processed.append(node)#将该节点标记为处理过
        node=find_lowest_cost_node(costs) #查找接下来要循环处理的点，并循环

**全部代码**

""" 第一个散列表 用于表示图 """
    graph={ }
    #起点 到各邻居的关系
    graph["start"]={ }
    graph["start"]["a"]=6
    graph["start"]["b"]=2
    #print(graph["start"].keys())#dict_keys(['a', 'b'])
    #节点a到各邻居关系
    graph["a"]={ }
    graph["a"]["fin"]=1
    
    #节点b到各邻居关系
    graph["b"]={ }
    graph["b"]["a"]=3
    graph["b"]["fin"]=5
    
    #终点与各邻居关系
    graph["fin"]={ }#终点没有邻居
    
    """ 第二个散列表 节点的开销。节点的开销表示起点出发到该节点需要多少时间，每个节点都要列出来"""
    infinity=float("inf")#无穷大
    costs={ }
    costs['a']=6
    costs['b']=2
    costs['fin']=infinity
    
    """ 第三个散列表 存储 路径 . parents['a']="start"表示节点a的上一节点是start,如果后面发现更短路径，可以修改为parents['a']=b，每个节点都要列出来"""
    parents={ }
    parents['a']="start"
    parents['b']="start"
    parents['fin']=None#出发点不能直接到达
    
    
    """ 需要一个数组，存储已经处理过的节点 """
    processed=[]
    
    """ 开销最小的函数 """
    def find_lowest_cost_node(costs):
        lowest_cost=float('inf')
        lowest_cost_node=None
        for node in costs:#遍历每个节点
            cost=costs[node]
            if cost<lowest_cost and node not in processed:#如果当前节点小于最小开销，且没有处理过
                lowest_cost_node=node #则将该节点设为最小开销节点
                lowest_cost=cost#更新最小开销
        return lowest_cost_node
    
    
    """ DiskStra算法"""
    node=find_lowest_cost_node(costs) #在未处理的节点中找到开销最小的节点，即离出发点最近的点
    while node  is not None: #这个循环表示所有节点处理过才会结束
        cost=costs[node]
        neighbors=graph[node]
        for n in neighbors.keys():#遍历当前节点的所有邻居
            new_cost=cost+neighbors[n]
            if costs[n]>new_cost:#如果经当前节点离该邻居更近
                costs[n]=new_cost#就更新该节点的开销
                parents[n]=node #同时将该邻居的父节点设置为该节点
        processed.append(node)#将该节点标记为处理过
        node=find_lowest_cost_node(costs) #查找接下来要循环处理的点，并循环
    
    
    #打印结果
    print('costs',costs)
    print('parents',parents)

![20210107145415628.png_pic_center][]

**流程图解**

找到开销最少的点  
![20210107150430383.png_pic_center][]

获取该节点的开销和邻居

![20210107150514700.png_pic_center][]

遍历邻居  
![20210107150552326.png_pic_center][]  
每个节点都要开销，开销指从起点到该节点需要多长时间，在这里，将计算从起点到B再到A的开销，而不是直接到A的开销

![20210107150752192.png_pic_center][]

和原始开销进行对比

![20210107150832953.png_pic_center][] 找到一条前往节点A的更短路径，更新节点A的开销 ![20210107150943153.png_pic_center][] 这条路径由B到A，由此更新节点A的父节点 ![20210107151039108.png_pic_center][]

现在回到for循环，下一个邻居是终点  
![20210107151216788.png_pic_center][]

经节点B前往终点需要7分钟，  
![2021010715132996.png_pic_center][]

原始终点节点开销为无穷大，现在7分钟，更新终点节点的开销和父节点  
![20210107151443950.png_pic_center][]

现在将节点B设为被处理过的

![2021010715152995.png_pic_center][]

接下来要处理的点

![20210107152016615.png_pic_center][] 获取节点A的开销和邻居 ![20210107152056832.png_pic_center][]

节点A只有一个邻居，终点。当前前往终点需要7分钟，经过节点A需要多久，见图

![20210107152148256.png_pic_center][]

更短，更新终点的开销和父节点  
![20210107152259633.png_pic_center][]

节点A被添加进处理过的。  
接下来要处理的点为终点fin。  
终点fin没有邻居，不更新，然后显示终点也被添加进处理过的。  
node变为空，退出while循环。结束。

如果要改变起点，如起点改到A，再来探讨该问题。只需修改costs和parents散列表即可。  
算例1借鉴：《算法图解》

## 算例2实现 ##

算例1用到的数据结构是散列表，本例子用矩阵来做。  
![20210108134030585.png_pic_center][]

**第一步：定义图和拓扑结构**

""" 一.定义图 """
    ### ====================给一个所有节点的列表
    list_nodes_id = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
    ### ==================== 给一个拓扑的常数矩阵.
    fin= float('inf') # 无穷大。这意味着没有联系。
    ### fin_topo是表示拓扑的二维邻接矩阵
    fin_topo = [
        [fin, 2.9, 2.5, fin, 2, fin, 1.8, 3, 1.8, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 0
        [2.9, fin, 1.3, fin, fin, 1.7, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 1
        [1, 1, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 2
        [fin, fin, 1, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 3
        [1, fin, fin, 1, fin, fin, fin, fin, fin, 1, 1, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 4
        [fin, 1, fin, fin, fin, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 5
        [1, fin, fin, fin, fin, 1, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 6
        [1, fin, fin, fin, fin, fin, 1, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 7
        [1, fin, fin, fin, fin, fin, fin, 1, fin, 1, fin, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin],  # 8
        [fin, fin, fin, fin, 1, fin, fin, fin, 1, fin, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 9
        [fin, fin, fin, fin, 1, fin, fin, fin, fin, fin, fin, 1, fin, 1, fin, fin, fin, fin, fin, fin, fin],  # 10
        [fin, fin, fin, fin, 1, fin, fin, fin, fin, 1, 1, fin, fin, 1, 1, fin, fin, fin, fin, fin, fin],  # 11
        [fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, fin, fin, fin, fin, 1, fin, fin, fin, fin, fin, fin],  # 12
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, 1, fin, fin, 1, fin, fin, 1, 1, fin, fin],  # 13
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, 1, 1, fin, 1, 1, fin, fin, fin, fin],  # 14
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, 1, fin, 1, 1, fin],  # 15
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, 1, fin, fin, fin, fin, 1],  # 16
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, fin, fin, fin, 1, fin, fin],  # 17
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, 1, fin, 1, fin, 1, fin],  # 18
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, fin, 1, fin, 1],  # 19
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, fin, 1, fin],  # 20
    ]
    
    ### --- 读取拓扑，并生成给定拓扑中的所有边。
    edges = []
    for i in range(len(fin_topo)):
        for j in range(len(fin_topo[0])):
            if i != j and fin_topo[i][j] != fin:
                edges.append((i, j, fin_topo[i][j]))  ### (i,j) 是一个链接;fin_topo[i][j]这里是1，链接的长度(i,j).
    #print(edges)
    #[(0, 1, 2.9), (0, 2, 2.5), (0, 4, 2), (0, 6, 1.8), (

edges  
![20210108140005760.png_pic_center][]

**第二步 算法**

"""算法实现"""
    from collections import defaultdict
    from heapq import *
    
    #heapq 堆，一般指最小堆
    """ heap = [1,3,4,2,6,8,9] heapq.heapify(heap) # heap = [1,2,4,3,6,8,9] """
    """ g {0: [(2.9, 1), (2.5, 2), (2, 4), (1.8, 6), (3, 7), (1.8, 8)], 1: [(2.9, 0), (1.3, 2), (1.7, 5)], 2: [(1, 0), (1, 1), (1, 3)], 3: [(1, 2), (1, 4)], 4: [(1, 0), (1, 3), (1, 9), (1, 10), (1, 11)], 5: [(1, 1), (1, 6)], 6: [(1, 0), (1, 5), (1, 7)], 7: [(1, 0), (1, 6), (1, 8)], 8: [(1, 0), (1, 7), (1, 9), (1, 12)], 9: [(1, 4), (1, 8), (1, 11)], 10: [(1, 4), (1, 11), (1, 13)], 11: [(1, 4), (1, 9), (1, 10), (1, 13), (1, 14)], 12: [(1, 8), (1, 14)], 13: [(1, 10), (1, 11), (1, 14), (1, 17), (1, 18)], 14: [(1, 11), (1, 12), (1, 13), (1, 15), (1, 16)], 15: [(1, 14), (1, 16), (1, 18), (1, 19)], 16: [(1, 14), (1, 15), (1, 20)], 17: [(1, 13), (1, 18)], 18: [(1, 13), (1, 15), (1, 17), (1, 19)], 19: [(1, 15), (1, 18), (1, 20)], 20: [(1, 16), (1, 19)]}) """
    
    def dijkstra_raw(edges, from_node, to_node):
        g = defaultdict(list)#使用list作第一个参数，可以很容易将键-值对序列转换为列表字典。
        for l, r, c in edges:
            g[l].append((c, r))
        q, seen = [(0, from_node, ())], set()#q=[(0, from_node, ())],q为当前节点创建一个堆
        while q:
            (cost, v1, path) = heappop(q)#删除q中的顶
            if v1 not in seen:#如果V1没有被查看,V1为出发点
                seen.add(v1)#将V1添加进已查看
                path = (v1, path)#（点，路径）
                if v1 == to_node:#如果当前点是目标点
                    return cost, path#返回距离和路径
                for c, v2 in g.get(v1, ()):#遍历V1的所有邻居 c为到邻居的距离，V2为邻居
                    if v2 not in seen:
                        heappush(q, (cost + c, v2, path))#修改起点到V2的距离
        return float("inf"), []

全部代码

""" 一.定义图 """
    # ====================给一个所有节点的列表
    list_nodes_id = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
    ### ==================== 给一个拓扑的常数矩阵.
    fin= float('inf') # 无穷大。这意味着没有联系。
    #fin_topo是表示拓扑的二维邻接矩阵
    fin_topo = [
        [fin, 2.9, 2.5, fin, 2, fin, 1.8, 3, 1.8, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 0
        [2.9, fin, 1.3, fin, fin, 1.7, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 1
        [1, 1, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 2
        [fin, fin, 1, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 3
        [1, fin, fin, 1, fin, fin, fin, fin, fin, 1, 1, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 4
        [fin, 1, fin, fin, fin, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 5
        [1, fin, fin, fin, fin, 1, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 6
        [1, fin, fin, fin, fin, fin, 1, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 7
        [1, fin, fin, fin, fin, fin, fin, 1, fin, 1, fin, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin],  # 8
        [fin, fin, fin, fin, 1, fin, fin, fin, 1, fin, fin, 1, fin, fin, fin, fin, fin, fin, fin, fin, fin],  # 9
        [fin, fin, fin, fin, 1, fin, fin, fin, fin, fin, fin, 1, fin, 1, fin, fin, fin, fin, fin, fin, fin],  # 10
        [fin, fin, fin, fin, 1, fin, fin, fin, fin, 1, 1, fin, fin, 1, 1, fin, fin, fin, fin, fin, fin],  # 11
        [fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, fin, fin, fin, fin, 1, fin, fin, fin, fin, fin, fin],  # 12
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, 1, fin, fin, 1, fin, fin, 1, 1, fin, fin],  # 13
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, 1, 1, fin, 1, 1, fin, fin, fin, fin],  # 14
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, 1, fin, 1, 1, fin],  # 15
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, 1, fin, fin, fin, fin, 1],  # 16
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, fin, fin, fin, 1, fin, fin],  # 17
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, 1, fin, 1, fin, 1, fin],  # 18
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, fin, 1, fin, 1],  # 19
        [fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, fin, 1, fin, fin, 1, fin],  # 20
    ]
    
    #--- 读取拓扑，并生成给定拓扑中的所有边。
    edges = []
    for i in range(len(fin_topo)):
        for j in range(len(fin_topo[0])):
            if i != j and fin_topo[i][j] != fin:
                edges.append((i, j, fin_topo[i][j]))  ### (i,j) 是一个链接;fin_topo[i][j]这里是1，链接的长度(i,j).
    #print(edges)
    #[(0, 1, 2.9), (0, 2, 2.5), (0, 4, 2), (0, 6, 1.8), (
    
    #算法实现
    from collections import defaultdict
    from heapq import *
    
    
    
    
    def dijkstra_raw(edges, from_node, to_node):
        g = defaultdict(list)#使用list作第一个参数，可以很容易将键-值对序列转换为列表字典。
        for l, r, c in edges:
            g[l].append((c, r))
        q, seen = [(0, from_node, ())], set()#q=[(0, from_node, ())],q为当前节点创建一个堆
        while q:
            (cost, v1, path) = heappop(q)#删除q中的顶
            if v1 not in seen:#如果V1没有被查看,V1为出发点
                seen.add(v1)#将V1添加进已查看
                path = (v1, path)#（点，路径）
                if v1 == to_node:#如果当前点是目标点
                    return cost, path#返回距离和路径
                for c, v2 in g.get(v1, ()):#遍历V1的所有邻居 c为到邻居的距离，V2为邻居
                    if v2 not in seen:
                        heappush(q, (cost + c, v2, path))
        return float("inf"), []
    
    start = int(input("请输入起始点："))
    end = int(input("请输入终点："))
    print("=== Dijkstra算法 ===")
    print("找从 %s 到 %s的最短路径:" % (start, end))
    length, path_queue = dijkstra_raw(edges,start, end)#path_queue路径
    print('距离',length)
    print('路径',path_queue)

![20210108152745191.png_pic_center][]

0到15的距离为4.8，路径0-8-12-14-15

## 工具包讲解 ##

参考我以前的博文  
[最短路径Dijkstra讲解，工具包使用 python  
][Dijkstra_ python]  
![在这里插入图片描述][20210107152546216.jpg_pic_center]

作者：电气-余登武

[20210107104713741.png_pic_center]: /images/20221119/ba35e56ff6fd4f90a1bf9df00dda006b.png
[20210107105154741.png_pic_center]: /images/20221119/9e63e4542a454632861270fc3d43b010.png
[BFS_python]: https://blog.csdn.net/KOBEYU652453/article/details/112172645
[20210107105438851.png_pic_center]: /images/20221119/7544d13e18e8409f9100ba3989c9ff82.png
[20210107125941706.png_pic_center]: /images/20221119/fbba067a3f19488aa956782cedd44e4f.png
[20210107130214244.png_pic_center]: /images/20221119/54d7da36087f4a43a0ad033d1db0a59b.png
[20210107130655480.png_pic_center]: /images/20221119/196daffa7453450da8ce622fb222dc26.png
[20210107130909689.png_pic_center]: /images/20221119/745bf3c5dc664823a404004efdcf9382.png
[20210107131007381.png_pic_center]: /images/20221119/94e883873f274cddb26a921ce31e2435.png
[20210107132756947.png_pic_center]: /images/20221119/fc9e6fff73d14ff88fd8af8454cc5184.png
[20210107135115447.png_pic_center]: /images/20221119/ec8b2a4110874fddaa0514b2e914c5ce.png
[20210107144301298.png_pic_center]: /images/20221119/f027a44106e84ffb85139a413b08f5ae.png
[20210107145415628.png_pic_center]: /images/20221119/2a32ad4c07174bd7a9176476e349255f.png
[20210107150430383.png_pic_center]: /images/20221119/e7e88fd715cc41a39ecc7780d28e1787.png
[20210107150514700.png_pic_center]: /images/20221119/9c1029cf959b4b16877282dbf9131a69.png
[20210107150552326.png_pic_center]: /images/20221119/ded95397ab0145b3a72802fedfd7bad8.png
[20210107150752192.png_pic_center]: /images/20221119/f06ba675f6e74d74988d03f5d67897dc.png
[20210107150832953.png_pic_center]: https://img-blog.csdnimg.cn/20210107150832953.png#pic_center
[20210107150943153.png_pic_center]: https://img-blog.csdnimg.cn/20210107150943153.png#pic_center
[20210107151039108.png_pic_center]: /images/20221119/170eed94d6a34e4c8fc9ee98fb8abd8f.png
[20210107151216788.png_pic_center]: /images/20221119/b3487dc72b10412498a3e250293e8da7.png
[2021010715132996.png_pic_center]: /images/20221119/849661d289c04e3ba936db86dd5fac87.png
[20210107151443950.png_pic_center]: /images/20221119/2fa5860c97c34a00bef1380f7f90afb4.png
[2021010715152995.png_pic_center]: /images/20221119/0feb943f86f94ac58a41ec414aaa78de.png
[20210107152016615.png_pic_center]: https://img-blog.csdnimg.cn/20210107152016615.png#pic_center
[20210107152056832.png_pic_center]: /images/20221119/d7cfa7474b624206bc4760f2ba1946e9.png
[20210107152148256.png_pic_center]: /images/20221119/8453f71fd3804c1598e1f533dd114b4a.png
[20210107152259633.png_pic_center]: /images/20221119/d423413440004e63bedc4601e44eb538.png
[20210108134030585.png_pic_center]: /images/20221119/f3a4ea91398c46009202694f08d1c37b.png
[20210108140005760.png_pic_center]: /images/20221119/3cd673cd2d4b4a30a861f51043b95b6e.png
[20210108152745191.png_pic_center]: /images/20221119/78af904c4a8d46db8f114481cccf88c0.png
[Dijkstra_ python]: https://blog.csdn.net/kobeyu652453/article/details/106600778
[20210107152546216.jpg_pic_center]: /images/20221119/cc75eb15e7fa4112b1ea9a4427d4e9e6.png