ダイクストラ法の変数が何を表しているのか

Question

基本情報技術者のアルゴリズム対策として、pythonで実際にコードを書いて学習しています。
本を見ながら勉強しているのですが、ダイクストラ法で出てくる変数が何を表しているのか、何の役割なのか、わからなくなってしまいました。
私がわからないと思った変数は、r,q,i,uの4つです。
大変困っています。よろしくお願いいたします。

    def dijkstra(edges, num_v):
    dist = [float('inf')] * num_v
    dist[0] = 0
    q = [i for i in range(num_v)]

    while len(q) > 0:
        # 最もコストが小さい頂点を探す
        r = q[0]
        for i in q:
            if dist[i] < dist[r]:
                r = i

        # 最もコストが小さい頂点を取り出す
        u = q.pop(q.index(r))
        for i in edges[u]:
            if dist[i[0]] > dist[u] + i[1]:
                # 頂点までのコストが更新できれば更新
                dist[i[0]] = dist[u] + i[1]

    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))
コード

Answer 1

コメントでは書ききれないので、回答の続きを別の回答として書きたいと思います。

求めらえているのは、dijkstra(edges, 7)の結果です。
最初の引数edgesがグラフの辺の情報、二つ目の引数 7 が頂点の数です。

destは、始点からの距離を格納する配列です。

    dist = [float('inf')] * num_v
    dist[0] = 0

のところで、dest = [0,∞,∞,∞,∞,∞,∞] が入ります。
最短距離を求める問題なので、無限大(∞)は"まだ不明"を表す。

「 # 最もコストが小さい頂点を探す」というコメントの２行下から「for i in q:」というforループがありますよね。
コメントの内容と、q = [i for i in range(num_v)]というqの初期値から、qは頂点の番号のリストだろうと推測できます。（コメントは大きなヒントになる事が多いので、丁寧に読んで下さい）

whileループがコメントの上の行で始まっていて、whileの条件が"len(q) > 0:" ですから、ループの中で配列qがだんだん短くなっていって、qが空っぽになったらプログラムが完了するのだと判断できます。

whileループの中は、「 # 最もコストが小さい頂点を探す」と「# 最もコストが小さい頂点を取り出す」の部分に分かれています。

「 # 最もコストが小さい頂点を探す」の部分

        r = q[0]
        for i in q:
            if dist[i] < dist[r]:
                r = i

は、rの初期値がq[0]で始点(0)。forループで頂点rよりも距離の短い頂点が見つかったら、それをrに代入していきます。ループが終わったらrに最も距離が近い頂点の番号が入っています。

「# 最もコストが小さい頂点を取り出す」の部分

        u = q.pop(q.index(r))
        for i in edges[u]:
            if dist[i[0]] > dist[u] + i[1]:
                # 頂点までのコストが更新できれば更新
                dist[i[0]] = dist[u] + i[1]

配列qのr番目が最も距離が近い頂点なので、それをpopで取り出します。（配列qの長さが１短くなります）
そして、取り出した頂点(u)から出ている辺のリスト(edges[u])の中で、これまでで判っている距離(dist[i[0]])と、リストの辺をたどった先までの距離(dist[u] + i[1]:)を比較して、辺をたどったほうが近ければ、距離を短いほうに更新します。

uを0だとすると、edgesuは、[[1, 4], [2, 3]]になります。
そうすると、for i in edges[u]のループで、iには、[1, 4]、[2, 3]が入ります。

r,q,u,iの順で変数の意味を説明しましたので、参考にしてください。

Comments

[coco_bauer]

「明らかなこと（＝確定できそうなノード）」は、最短距離のノードです。最短距離を見つけようとするのですから、「距離が遠いノードを選んではダメだ」というのは明らかではないでしょうか？

[lime_penguins]

ご回答ありがとうございます。
ずっとわからず悩んでいたのですが、この回答を読んで理解することができました！わかりやすかったです。
ここから進むことができず困っていたので、大変助かりました。
ありがとうございます！

Answer 2

ダイクストラ法（最短経路問題） の記事がダイクストラ法の動作を判りやすく図解しているので参考にすると良いと思います。

Comments

[lime_penguins]

ありがとうございます。
ダイクストラ法の流れは大分掴めたのですが、サイトで記載されている「明らかなこと（＝確定できそうなノード）」は、今回のプログラムのどこで表されているのでしょうか？
q = [i for i in range(num_v)]のところかな？と思ったのですが、range(0, 7)ですし…。
始めたばかりでよくわからないので、教えていただければと思います。