[概念整理]マルチゾーンアルゴリズム

最短経路問題では,ある頂点から別の頂点への最短費用を求めるアルゴリズムである.多益アルゴリズムは貪欲アルゴリズムに似ている.現在の頂点で到達可能なすべての頂点を決定し、その中から最もコストの低い頂点を選択して最適な選択を行います.
動作はBFSに似ている.現在の頂点に到達可能なすべての頂点をhipに挿入し、その中から最もコストの低いノードを選択して最短のパスを更新します.
複数のバンドアルゴリズムを実装するデータ構造は優先順位キューを用いることができるが,Pythonではほとんどが最小hipを用いる.(構造の親ノードの値が最小)

1.例

次のグラフがある場合、Aから各頂点への最小コストパスを求めるという問題を考慮します.

2.マルチアウトレットアルゴリズムの応用方式

1)頂点間の最小距離を保存する必要があり、開始ノードAは0を保存します.そして残りを無限大に貯蔵します.
[0, ∞, ∞, ∞, ∞ ]
2)優先キュー(最小HIP)に開始ノード距離Aの距離0を追加する.ここでAの距離とはAからAまでの距離のことで、もちろん0です.
3)優先キューから最初に入れた0を抽出する.

4)抽出ノードAにおける可動ノードの距離と、アレイに格納された距離とを比較する.
->Aで移動可能なノードはBとCであり,頂点間距離を格納する配列ではAを除くすべてのノードが無限に格納され,BとC間の距離も無限である.
->それで、BとA、CとAの距離がそれぞれ無限大から10と3に更新!!

5)その後、配列内のデータが更新されると、優先キューに挿入されます.

ここで、キューは最小要素が一番前、3が一番前になるように並べ替えられます.
6)その後、優先キューから取り出すデータがなくなるまで、この手順を繰り返します.
ここから混同されるかもしれません.ここからはしっかり見ていきます.
7)優先キューから最小要素3を抽出し、3に接続されたノードCにおける移動可能ノードの距離とアレイに格納された距離とを比較してキューを更新する.

この場合,比較距離は無限大と4,無限大と2,無限大と8で置き換えられるわけではない.最初の元素Aを基準として行う.
•初めてAからBまでのコストは10ですが、AからC、Bまでのコストは7で、10から7に更新されます.
•AからCからDまでの費用は無限で、11に更新されます.
•AからCからEまでのコストは無限で、5に更新されます.
8)優先キューから最小要素5を再び抽出し、5に接続されたノードDにおける移動可能なノードの距離とアレイに格納された距離とを比較することによってキューを更新する.

ここではAからEまでのコストを比較し、既存の5より大きく、交換しない.を選択すると、残りのキューの要素が比較されます.
9)7に接続されたノードBにおける可動ノードの距離をアレイに格納された距離と比較し、再更新する.

10)その後、再度同じ比較作業を行いますが、このとき9~11間の距離もキューから削除されます.

11)最終的に9から再開する.AからDまでの費用は前の頂点を通過し、累計は9となる.

その後再度AからEまでのコストについて調査した結果,既存のコスト5をより低価格で置き換えることなくキュー探索を終了した.
したがって,最終的な答えは[0,7,3,9,5]である.

3.解答

優先順位キューを使用するには、最小hipモジュールheapqを使用します.

import heapq
import sys

graph = {
    "A": {"B": 10, "C": 3},
    "B": {"C": 1, "D": 2},
    "C": {"B": 4, "D": 8, "E": 2},
    "D": {"E": 7},
    "E": {"D": 9}
}


def dijkstara(start):
    distances = {node: sys.maxsize for node in graph}
    distances[start] = 0
    queue = []

    heapq.heappush(queue, (distances[start], start))

    while queue:
        current_distance, node = heapq.heappop(queue)
        if distances[node] < current_distance:
            continue

        for neighbor_node, distance in graph[node].items():
            weighted_distance = current_distance + distance
            if weighted_distance < distances[neighbor_node]:
                distances[neighbor_node] = weighted_distance
                heapq.heappush(queue, (weighted_distance, neighbor_node))

    return distances

result = dijkstara("A")