ダイクストラ法 優先度付きキューについて

Question

優先度付きキューを使ったダイクストラ法を学んでいるのですが、キューを作成したあたりから理解が追いつかず困っています。

def min_heapify(data, i):
    left = 2 * i + 1
    right = 2 * i + 2
    min = i
    if left < len(data) and data[i][0] > data[left][0]:
        min = left
    if right < len(data) and data[min][0] > data[right][0]:
        min = right
    if min != i:
        data[i], data[min] = data[min], data[i]
        min_heapify(data, min)
```ヒープソートで、先頭の要素を最も小さい値にする工程なのだと、ここまでは自分なりに理解ができました。
```python
def dijkstra(edges, num_v):
    dist = [float('inf')] * num_v
    dist[0] = 0
    q = [[0, 0]]
```各頂点に∞を入れて、最初の頂点までのコストは０にしている。
キューを作成して[0, 0]を入れた。
という認識です。

```python
    while len(q) > 0:
        # キューから最小の要素を取り出し
        q[0], q[-1] = q[-1], q[0]
        _, u = q.pop()
        # キューを再構成
        min_heapify(q, 0)
        # 各辺に対してコストを調べる
        for i in edges[u]:
            if dist[i[0]] > dist[u] + i[1]:
                dist[i[0]] = dist[u] + i[1]
                q.append([dist[u] + i[1], i[0]])
                j = len(q) - 1
                while (j > 0) and (q[(j - 1) // 2] > q[j]):
                    q[(j - 1) // 2], q[j] = q[j], q[(j - 1) // 2]
                    j = (j - 1) // 2

    return dist

edges = [
    [[1, 4], [2, 3]],
    [[2, 1], [3, 1], [4, 5]],
    [[5, 2]],
    [[4, 3]],
    [[6, 2]],
    [[4, 1], [6, 4]],
    []
]
print(dijkstra(edges, 7))
```ここからわからなくなってしまいました。
qに何か数字が残っていた場合、キューから最小の要素を取り出し、各辺に対してコストを調べる、と書かれていますが、いまいち流れが掴めません。
具体的な数字を入れて説明していただけると、大変ありがたいです。
よろしくお願いいたします。

Comments

[ockeghem]

なにを元に学んでいるのか出典を示してください

[lime_penguins]

失礼致しました。
Pythonではじめるアルゴリズム入門
という本です。

Answer 1

初期状態ではリストdistは、

dist: [0, inf, inf, inf, inf, inf, inf]

となっていますが、Aを起点に、A→Bのコストが4、A→Cのコストが3ですよね。Aから直接到達できるこれらを処理すると、

dist: [0, 4, 3, inf, inf, inf, inf]

となります。この段階でキューを示すリストqは空です。初期値 q = [[0, 0]] ですが、この値はループの先頭でpopしているからです。ここで、A→Bの距離4、A→Cの距離3をqにappendして、j = len(q) - 1 以下のwhileループでヒープ(q)を再構成しています（ここはちょっとスマートでないと思いました）。その結果、qは下記となります。

q: [[3, 2], [4, 1]]

リスト[3, 2]は、始点Aからの距離が3、地点がC(=2)ということです。同様に[4, 1]は、距離=4、地点=Bですね。qはヒープなので、距離最小値の[3, 2]が先頭にあります。
ダイクストラ法は、距離最小値の[3, 2]について処理をすればよいので、キューからこれをとりだし、残りをmin_heapifyします。
[3, 2]を取り出したことで、着眼点がC=2となりますので、Cからの距離を調べていきます。これは[5, 2]ですので、地点5(F)までの距離は3+2=5です。そこで、リストdistは下記になります。

dist: [0, 4, 3, inf, inf, 5, inf]

そして、qに距離5、地点5ということで、[5, 5]を追加します。qは下記となります。

q: [[4, 1], [5, 5]]

次の距離最小値点はB(=1)、距離は4ですので、同様の処理を地点Bに対して行います。以下同様となります。

Comments

[lime_penguins]

ご回答ありがとうございます！
少々時間がかかってしまいましたが、しっかり理解することができました。
たしかに、whileループでヒープ(q)を再構成を再構成しているところは、無駄な経路があるように感じました。
なかなか一人では理解できなかったので、大変助かりました。