栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

狄克斯特拉(Dijkstra)算法python实现

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

狄克斯特拉(Dijkstra)算法python实现

狄克斯特拉(Dijkstra)算法 1.算法原理

已知图 G = ( V , E ) G=(V,E) G=(V,E),将其节点集分为两组:置定节点集 G p G_p Gp​和未置定节点集 G − G p G-G_p G−Gp​。其中 G p G_p Gp​内的所有置定节点,是指定点 v s v_s vs​到这些节点的路径为最短(即已完成最短路径的计算)的节点。而 G − G p G-G_p G−Gp​内的节点是未置定节点,即 v s v_s vs​到未置定节点距离是暂时的,随着算法的下一步将进行不断调整,使其成为最短径。

在调整各未置定节点的最短径时,是将 G p G_p Gp​中的节点作为转接点。具体地说,就是将 G p G_p Gp​中的节点作为转接点,计算 ( v s , v j ) (v_s ,v_j) (vs​,vj​)的径长 ( v j ∈ G − G p ) (v_jin G-G_p) (vj​∈G−Gp​),若该次计算的径长小于上次的值,则更新径长,否则,径长不变。计算后取其中径长最短者,之后将 v j v_j vj​划归到 G p G_p Gp​中。当 ( G − G p ) (G-G_p) (G−Gp​)最终成为空集,同时 G p = G G_p=G Gp​=G,即求得 v s v_s vs​到所有其他节点的最短路径。

2.举例

如图

首先写出它的邻接矩阵,由于默认不考虑自环(即一个点有一条路径连接自己)的情况,所以规定一个点到它自己的距离为0,同时规定两个点之间如果无法直接到达则距离为 ∞ infin ∞
( 0 2 5 1 ∞ ∞ 2 0 3 2 ∞ ∞ 5 3 0 3 1 5 1 2 3 0 1 ∞ ∞ ∞ 1 1 0 2 ∞ ∞ 5 ∞ 2 0 ) begin{pmatrix} 0 & 2 & 5 & 1 & infin & infin \ 2 & 0 & 3 & 2 & infin & infin \ 5 & 3 & 0 & 3 & 1 & 5 \ 1 & 2 & 3 & 0 & 1 & infin \ infin & infin & 1 & 1 & 0 & 2 \ infin & infin & 5 & infin & 2 & 0 end{pmatrix} ⎝⎜⎜⎜⎜⎜⎜⎛​0251∞∞​2032∞∞​530315​12301∞​∞∞1102​∞∞5∞20​⎠⎟⎟⎟⎟⎟⎟⎞​
现计算节点 v 1 v_1 v1​到其他节点的最短路径

初始时,置定节点集 G = { } G={} G={},未置定节点集 G − G P = { v 1 , v 2 , v 3 , v 4 , v 5 , v 6 } G-G_P={v_1,v_2,v_3,v_4,v_5,v_6} G−GP​={v1​,v2​,v3​,v4​,v5​,v6​}

先用一张表格总览一下整个迭代过程

迭代次数 v 1 , v 2 , v 3 , v 4 , v 5 , v 6 v_1,v_2,v_3,v_4,v_5,v_6 v1​,v2​,v3​,v4​,v5​,v6​置定节点 w i w_i wi​ G p G_p Gp​
0 ( 0 2 5 1 ∞ ∞ ) begin{pmatrix}0 & 2 & 5 & 1 & infin & infinend{pmatrix} (0​2​5​1​∞​∞​) v 1 v_1 v1​ w 1 = 0 w_1=0 w1​=0 { v 1 } {v_1} {v1​}
1 ( 2 5 1 ∞ ∞ ) begin{pmatrix}& & 2 & 5 & 1 & infin & infinend{pmatrix} (​​2​5​1​∞​∞​) v 4 v_4 v4​ w 4 = 1 w_4=1 w4​=1 { v 1 , v 4 } {v_1,v_4} {v1​,v4​}
2 ( 2 4 2 ∞ ) begin{pmatrix}& & 2 & 4 & & & 2 & infinend{pmatrix} (​​2​4​​​2​∞​) v 2 v_2 v2​ w 2 = 2 w_2=2 w2​=2 { v 1 , v 4 , v 2 } {v_1,v_4,v_2} {v1​,v4​,v2​}
3 ( 4 2 ∞ ) begin{pmatrix}& & & & 4 & & & 2 & infinend{pmatrix} (​​​​4​​​2​∞​) v 5 v_5 v5​ w 5 = 2 w_5=2 w5​=2 { v 1 , v 4 , v 2 , v 5 } {v_1,v_4,v_2,v_5} {v1​,v4​,v2​,v5​}
4 ( 3 4 ) begin{pmatrix}& & & & 3 & & & & & 4end{pmatrix} (​​​​3​​​​​4​) v 3 v_3 v3​ w 3 = 3 w_3=3 w3​=3 { v 1 , v 4 , v 2 , v 5 , v 3 } {v_1,v_4,v_2,v_5,v_3} {v1​,v4​,v2​,v5​,v3​}
5 ( 4 ) begin{pmatrix}& & & & & & & & & & 4end{pmatrix} (​​​​​​​​​​4​) v 6 v_6 v6​ w 6 = 4 w_6=4 w6​=4 { v 1 , v 4 , v 2 , v 5 , v 3 , v 6 } {v_1,v_4,v_2,v_5,v_3,v_6} {v1​,v4​,v2​,v5​,v3​,v6​}

具体过程描述如下:

  1. 第0次迭代: ( 0 2 5 1 ∞ ∞ ) begin{pmatrix}0 & 2 & 5 & 1 & infin & infinend{pmatrix} (0​2​5​1​∞​∞​)
    • 看矩阵的第一行,它表示节点 v 1 v_1 v1​到其他节点的距离,选择其中最小的一个。
    • 显然 v 1 v_1 v1​到自身距离最短,为0。所以把 v 1 v_1 v1​加入置定节点集,同时移出未置定节点集, G p = { v 1 } G_p={v_1} Gp​={v1​}, G − G P = { v 2 , v 3 , v 4 , v 5 , v 6 } G-G_P={v_2,v_3,v_4,v_5,v_6} G−GP​={v2​,v3​,v4​,v5​,v6​},并记录下 v 1 v_1 v1​到 v 1 v_1 v1​的距离 w 1 = 0 w_1=0 w1​=0
  2. 第1次迭代: ( 2 5 1 ∞ ∞ ) begin{pmatrix}& & 2 & 5 & 1 & infin & infinend{pmatrix} (​​2​5​1​∞​∞​)
    • 由于 G p = { v 1 } G_p={v_1} Gp​={v1​},只有一个节点 v 1 v_1 v1​,还是看第一行,但去掉第一列,找最小的数。
    • 显然是 v 1 v_1 v1​到 v 4 v_4 v4​距离最小, w 4 = 1 w_4=1 w4​=1。所以把 v 4 v_4 v4​加入置定节点集,同时移出未置定节点集,此时 G p = { v 1 , v 4 } G_p={v_1,v_4} Gp​={v1​,v4​}, G − G P = { v 2 , v 3 , v 5 , v 6 } G-G_P={v_2,v_3,v_5,v_6} G−GP​={v2​,v3​,v5​,v6​}
    • 由于我们的 G p G_p Gp​中多了一个节点,也就是说在考虑 v 1 v_1 v1​到其他节点距离时有了一个中转点 v 4 v_4 v4​,那么 v 1 v_1 v1​到其他节点的距离可能会因为这个 v 4 v_4 v4​的存在而缩短,或者原来 v 1 v_1 v1​无法直接到达的点现在可以经过 v 4 v_4 v4​来到达。
      • 原来 v 1 v_1 v1​到 v 2 v_2 v2​的距离是2,如果经过 v 4 v_4 v4​再到 v 2 v_2 v2​距离是4,没有变小,所以不用改;
      • 原来 v 1 v_1 v1​到 v 3 v_3 v3​的距离是5,如果经过 v 4 v_4 v4​再到 v 3 v_3 v3​距离是4( v 1 v_1 v1​到 v 4 v_4 v4​的距离是1, v 4 v_4 v4​再到 v 3 v_3 v3​的距离是3)比原来的小了,需要修改;
      • 原来 v 1 v_1 v1​无法到达 v 5 v_5 v5​,但经过 v 4 v_4 v4​后可以到达,距离为2,需修改:
      • 原来 v 1 v_1 v1​无法到达 v 6 v_6 v6​,经过 v 4 v_4 v4​仍无法到达,不用改
    • 至此, v 1 v_1 v1​到其他节点的距离被更新为 ( 2 4 2 ∞ ) begin{pmatrix}& & 2 & 4 & & & 2 & infinend{pmatrix} (​​2​4​​​2​∞​)
  3. 第2次迭代: ( 2 4 2 ∞ ) begin{pmatrix}& & 2 & 4 & & & 2 & infinend{pmatrix} (​​2​4​​​2​∞​)
    • 此时 G p = { v 1 , v 4 } G_p={v_1,v_4} Gp​={v1​,v4​},找最小的数
    • 到 v 2 v_2 v2​距离最小, w 2 = 2 w_2=2 w2​=2,把 v 2 v_2 v2​加入置定节点集,同时移出未置定节点集,此时 G p = { v 1 , v 4 , v 2 } G_p={v_1,v_4,v_2} Gp​={v1​,v4​,v2​}, G − G P = { v 3 , v 5 , v 6 } G-G_P={v_3,v_5,v_6} G−GP​={v3​,v5​,v6​}
    • 此时我们又多了一个中转点 v 2 v_2 v2​
      • 原来 v 1 v_1 v1​到 v 3 v_3 v3​距离是4,经过 v 2 v_2 v2​中转后距离是5,没有变小,不用改;
      • 原来 v 1 v_1 v1​到 v 5 v_5 v5​距离是2, v 2 v_2 v2​无法中转,不用改;
      • 原来 v 1 v_1 v1​无法到达 v 6 v_6 v6​,经过 v 2 v_2 v2​仍无法到达,不用改
    • 至此, v 1 v_1 v1​到其他节点的距离更新(其实完全没有更新)为 ( 4 2 ∞ ) begin{pmatrix}& & & & 4 & & & 2 & infinend{pmatrix} (​​​​4​​​2​∞​)
  4. 第3次迭代: ( 4 2 ∞ ) begin{pmatrix}& & & & 4 & & & 2 & infinend{pmatrix} (​​​​4​​​2​∞​)
    • 找最小
    • 到 v 5 v_5 v5​最小, w 5 = 2 w_5=2 w5​=2, G p = { v 1 , v 4 , v 2 , v 5 } G_p={v_1,v_4,v_2,v_5} Gp​={v1​,v4​,v2​,v5​}, G − G P = { v 3 , v 6 } G-G_P={v_3,v_6} G−GP​={v3​,v6​}
    • 又多了一个中转点 v 5 v_5 v5​
      • 原来 v 1 v_1 v1​到 v 3 v_3 v3​距离是4,经过 v 5 v_5 v5​中转后距离是3,变小了,需要修改;
      • 原来 v 1 v_1 v1​无法到达 v 6 v_6 v6​,经过 v 5 v_5 v5​后距离变成4,修改
    • 至此, v 1 v_1 v1​到其他节点的距离更新为 ( 3 4 ) begin{pmatrix}& & & & 3 & & & & & 4end{pmatrix} (​​​​3​​​​​4​)
  5. 第4次迭代: ( 3 4 ) begin{pmatrix}& & & & 3 & & & & & 4end{pmatrix} (​​​​3​​​​​4​)
    • 找最小
    • 到 v 3 v_3 v3​最小, w 3 = 3 w_3=3 w3​=3, G p = { v 1 , v 4 , v 2 , v 5 , v 3 } G_p={v_1,v_4,v_2,v_5,v_3} Gp​={v1​,v4​,v2​,v5​,v3​}, G − G P = { v 6 } G-G_P={v_6} G−GP​={v6​}
    • 又多了一个中转点 v 3 v_3 v3​
      • 原来 v 1 v_1 v1​到 v 6 v_6 v6​距离是4,经过 v 3 v_3 v3​中转后距离是8,没有变小,不用修改
    • 至此, v 1 v_1 v1​到其他节点距离更新为 ( 4 ) begin{pmatrix}& & & & & & & & & & 4end{pmatrix} (​​​​​​​​​​4​)
  6. 第5次迭代: ( 4 ) begin{pmatrix}& & & & & & & & & & 4end{pmatrix} (​​​​​​​​​​4​)
    • 找最小
    • w 6 = 4 w_6=4 w6​=4, G p = { v 1 , v 4 , v 2 , v 5 , v 3 , v 6 } G_p={v_1,v_4,v_2,v_5,v_3,v_6} Gp​={v1​,v4​,v2​,v5​,v3​,v6​}, G − G P = { } G-G_P={} G−GP​={}
    • G − G P G-G_P G−GP​空了,说明找完了,迭代结束

结果如下表所示

节点 v 1 v_1 v1​ v 2 v_2 v2​ v 3 v_3 v3​ v 4 v_4 v4​ v 5 v_5 v5​ v 6 v_6 v6​
最短路径 { v 1 } {v_1} {v1​} { v 1 , v 2 } {v_1,v_2} {v1​,v2​} { v 1 , v 4 , v 5 , v 3 } {v_1,v_4,v_5,v_3} {v1​,v4​,v5​,v3​} { v 1 , v 4 } {v_1,v_4} {v1​,v4​} { v 1 , v 4 , v 5 } {v_1,v_4,v_5} {v1​,v4​,v5​} { v 1 , v 4 , v 5 , v 6 } {v_1,v_4,v_5,v_6} {v1​,v4​,v5​,v6​}
径长023124

实现代码:

import copy

# 首先给出邻接矩阵,两个节点之间距离无穷大用-1表示
matrix = [[0, 2, 5, 1, -1, -1],
          [2, 0, 3, 2, -1, -1],
          [5, 3, 0, 3, 1, 5],
          [1, 2, 3, 0, 1, -1],
          [-1, -1, 1, 1, 0, 2],
          [-1, -1, 5, -1, 2, 0]]


def dijkstra(adjacent_matrix):
    # 获取节点数
    node_number = len(adjacent_matrix)

    # 置定节点集
    G_p = []

    # 未置定节点集
    g_p = []

    # 全部的节点集,用数字表示节点
    G = []

    for i in range(node_number):
        G.append(i + 1)
        g_p.append(i + 1)

    # 用一个一维数组表示v_s节点到其他结点的距离,初始时,这个距离就是邻接矩阵的第s行
    s = 1
    distance = copy.deepcopy(adjacent_matrix[s - 1])

    # 记录路径和径长
    path = []
    w = copy.deepcopy(adjacent_matrix[s - 1])

    # 由于从v_s结点开始,路径的起点都是v_s
    for i in range(node_number):
        path.append([s])

    # 开始迭代
    for i in range(node_number):
        # 遍历整个列表,找最小值,初始时假定最小值为最大值
        min_value = max(distance)
        min_index = distance.index(min_value)
        for j in range(len(distance)):
            if 0 <= distance[j] < min_value:
                min_value = distance[j]
                min_index = j
        # 找到索引为min_index的节点是到v_s距离最短的,把他加入G_p中,并从g_p中移除,同时记录下最短距离
        G_p.append(min_index + 1)
        g_p.remove(min_index + 1)
        w[min_index] = min_value
        # -2表示这个点已经被选过了
        distance[min_index] = -2

        # 更新G_p后,需要对distance进行更新
        # 对distance中的每一个数据,当添入新节点后是否有变化
        # 只需考虑g_p中的节点即可
        for j in g_p:
            # 如果索引为min_index的节点可以到达v_j,并且从v_s到min_value再到v_j的距离比原来从v_s到v_j的距离要小
            # 或者原来v_s无法到达v_j
            if adjacent_matrix[min_index][j-1] > 0 and (
                    adjacent_matrix[min_index][j-1] + min_value < distance[j-1]
                    or distance[j-1] == -1):
                distance[j-1] = adjacent_matrix[min_index][j-1] + min_value
                for item in path[min_index]:
                    path[j-1].append(item)
                path[j-1] = list(set(path[j-1]))
                path[j-1].append(min_index+1)

        print("第%d次迭代:" % i, distance, path, w)


dijkstra(matrix)

代码输出结果如下:

'''
迭代次数:[节点选择情况] [最短路径] [所选节点到每个节点的最小距离]
第0次迭代: [-2, 2, 5, 1, -1, -1] [[1], [1], [1], [1], [1], [1]] [0, 2, 5, 1, -1, -1]
第1次迭代: [-2, 2, 4, -2, 2, -1] [[1], [1], [1, 4], [1], [1, 4], [1]] [0, 2, 5, 1, -1, -1]
第2次迭代: [-2, -2, 4, -2, 2, -1] [[1], [1], [1, 4], [1], [1, 4], [1]] [0, 2, 5, 1, -1, -1]
第3次迭代: [-2, -2, 3, -2, -2, 4] [[1], [1], [1, 4, 5], [1], [1, 4], [1, 4, 5]] [0, 2, 5, 1, 2, -1]
第4次迭代: [-2, -2, -2, -2, -2, 4] [[1], [1], [1, 4, 5], [1], [1, 4], [1, 4, 5]] [0, 2, 3, 1, 2, -1]
第5次迭代: [-2, -2, -2, -2, -2, -2] [[1], [1], [1, 4, 5], [1], [1, 4], [1, 4, 5]] [0, 2, 3, 1, 2, 4]
'''
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/917666.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号