Skip to content

Python でダイクストラ法を実装する (写経)

tomson784 の ダイクストラ法をPythonで実装 を写経してみました。 構成図は転記しません。 しっかり理解した場合は是非、tomson784 さんの元記事をどうぞ！

Python venv 環境の作成

1
2
3
4
5
6
mkdir dijkstra
cd dijkstra
python3 -m venv .venv
echo 'source .venv/bin/activate' > .envrc
direnv allow
python3 -m pip install --upgrade pip numpy

サンプルスクリプト

 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
import numpy as np

node_l = {
    "S":0,
    "A":np.inf,
    "B":np.inf,
    "C":np.inf,
    "D":np.inf,
    "E":np.inf,
    "F":np.inf,
    "G":np.inf
}

# 確定したルート
node_l_ = {}

edge = {
    "S":{"A":5, "B":4, "C":1},
    "A":{"S":5, "D":2},
    "B":{"S":4, "D":5, "E":6},
    "C":{"S":1, "B":2},
    "D":{"A":2, "B":5, "F":1, "G":3},
    "E":{"B":6, "G":2},
    "F":{"D":1, "G":3},
    "G":{"D":3, "E":2, "F":4}
}

while True:
    # 未確定ノードの中からルートが最小のノードの選択
    if len(node_l) == 1:
        min_edge = list(node_l.keys())[0]
    else:
        min_edge = min(node_l, key=node_l.get)

    # 探索したノード間のルートの削除
    del_list = []
    for i in edge:
        for j in edge[i]:
            if j == min_edge:
                del_list.append(i+j)
    for i in del_list:
        del edge[i[0]][i[1]]

    # 探索したノードのコストが以前のものより小さければ更新する
    for i,j in edge[min_edge].items():
        if (j + node_l[min_edge]) < node_l[i]:
            node_l[i] = j + node_l[min_edge]

    # 確定したノードへのルートの削除
    node_l_[min_edge] = node_l[min_edge]
    if len(edge) == 1:
        break
    del edge[min_edge]
    del node_l[min_edge]

    print("未確定のノード ", end="")
    print(node_l)
    print("確定したノード ", end="")
    print(node_l_)
    print("-"*100)

print("確定したノード ", end="")
print(node_l_)

実行結果

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# python3 dijkstra.py
未確定のノード {'A': 5, 'B': 4, 'C': 1, 'D': inf, 'E': inf, 'F': inf, 'G': inf}
確定したノード {'S': 0}
----------------------------------------------------------------------------------------------------
未確定のノード {'A': 5, 'B': 3, 'D': inf, 'E': inf, 'F': inf, 'G': inf}
確定したノード {'S': 0, 'C': 1}
----------------------------------------------------------------------------------------------------
未確定のノード {'A': 5, 'D': 8, 'E': 9, 'F': inf, 'G': inf}
確定したノード {'S': 0, 'C': 1, 'B': 3}
----------------------------------------------------------------------------------------------------
未確定のノード {'D': 7, 'E': 9, 'F': inf, 'G': inf}
確定したノード {'S': 0, 'C': 1, 'B': 3, 'A': 5}
----------------------------------------------------------------------------------------------------
未確定のノード {'E': 9, 'F': 8, 'G': 10}
確定したノード {'S': 0, 'C': 1, 'B': 3, 'A': 5, 'D': 7}
----------------------------------------------------------------------------------------------------
未確定のノード {'E': 9, 'G': 10}
確定したノード {'S': 0, 'C': 1, 'B': 3, 'A': 5, 'D': 7, 'F': 8}
----------------------------------------------------------------------------------------------------
未確定のノード {'G': 10}
確定したノード {'S': 0, 'C': 1, 'B': 3, 'A': 5, 'D': 7, 'F': 8, 'E': 9}
----------------------------------------------------------------------------------------------------
確定したノード {'S': 0, 'C': 1, 'B': 3, 'A': 5, 'D': 7, 'F': 8, 'E': 9, 'G': 10}