蟻本をpythonで: Sec.2-5 ダイクストラ法

ダイクストラ法は、与えられた重み付き無向グラフ上の2点間の最小距離を求める問題の解法で、負の重みのedgeが無い限りok。

解説を読んでもボヤッとしていたが、以下のようにもう一つグラフを作るような実装を考えた結果腑に落ちた。

実装のため、重み付きグラフのクラスに以下のメソッドを追加した。動作としては
1. from_nodeからto_nodeへのedgeを削除
2. 1でfrom_nodeが浮遊した場合グラフからfrom_nodeを削除

    def remove_wo_weight(self, from_node, to_node):

        if from_node in self:
            count = 0
            for [node, weight] in self[from_node]:
                if node == to_node:
                    self[from_node].pop(count)
                count += 1

            if self[from_node] == []:

                self.pop(from_node)

ダイクストラ法のコードは以下.

import mygraph

print("number of nodes")
N = int(input())

print("input graph")
graph = mygraph.WeightedGraph()

while 1:

    inputline = input()

    if inputline == "":
        break

    inputline = list(map(int, inputline.split()))

    graph.join(inputline[0], inputline[1], inputline[2])

graph = graph.undirected()


for node in graph:
    if not isinstance(graph[node][0], list):
        graph[node] = [graph[node]]

print("Start?")
startpos = int(input())
print("Goal?")
goalpos = int(input())


dp = N * [float("INF")]

minlength_graph = mygraph.WeightedGraph()

minlength_graph.join(startpos, startpos, 0)


while 1:

    shortest_comb = [0, 0, float("INF")]

    for min_node in minlength_graph:

        for [to_node, to_weight] in graph[min_node]:

            if shortest_comb[2] > minlength_graph.weight(startpos, min_node) + to_weight:

                shortest_comb = [min_node, to_node, minlength_graph.weight(
                    startpos, min_node) + to_weight]

    minlength_graph.join(startpos, shortest_comb[1], shortest_comb[2])

    for fixed_nodes in minlength_graph:

        graph.remove_wo_weight(fixed_nodes, shortest_comb[1])

        graph.remove_wo_weight(shortest_comb[1], fixed_nodes)

    if shortest_comb[1] == goalpos:

        print(shortest_comb[2])

        break

    minlength_graph = minlength_graph.undirected()

入力と出力は省略(ベルマンフォードの時と同じ)

初期位置と距離が確定した点を、その点までの距離をweightとして結んだグラフ = minlength_graphを作っていき、minlength_graphに含まれるnode間のedgeを元のgraphからgraph.remove_wo_weight()で削除していく。

要するにminlength_graphにdpリストの役目をさせているだけなのだけれど、視覚的(?)には分かりやすくなった気がする(以下gif)。

追記)
計算量のことを考えると、最小距離のnodeだけではなく、二番目に近いnodeまで記録しておいたほうがいい。そうすると、次のステップでは、新たに距離が確定した点に隣接した点までの距離と、前ステップで二番目に短かった点までの距離だけを比較すれば良いので無駄がなくなる。