ヒープを用いたダイクストラ法について

Question

「Pythonではじめるアルゴリズム入門」という本のダイクストラ法の解説にある
フローチャートとコードに間違いがあるように思うのですがどうでしょうか？

以下コードとフローチャートです。

#ヒープを作る関数
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)

#edges:辺のデータセット num_v:頂点の数
def dijkstra(edges, num_v):
    #dist:頂点ごとのコスト
    dist = [float('inf')] * num_v
    dist[0] = 0
    #q:[頂点のコスト、頂点の番号]
    q = [[0, 0]]

    while len(q) > 0:
        # キューから最小の要素を取り出し
        q[0], q[-1] = q[-1], q[0]
        #qの最後の要素を取り出し
        _, 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
                #末尾に付け加えた要素を適切な位置に
                #Pythonのリスト比較演算子は第1要素→第2要素の順に比較
                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))

ここで使われるヒープは親を子より小さくした構造なので、
「ダイクストラ法」のフローチャート右下にある

「親の方が小さい？」→(yes)「親と交換」

は

「親の方が大きい？」→(yes)「親と交換」

が適切だと思われます。
それに従いコード内の

while (j > 0) and (q[(j - 1) // 2] < q[j]):

も

while (j > 0) and (q[(j - 1) // 2] > q[j]):

となるはずです。
元のコードのままでも結局 q に入る値に関しては全て探索されるので
返り値自体に変化はないのですが、適切に最小値を選んでいないことにより
無駄な探索経路が増えることになると思うのですがどうでしょうか？

Answer 1

著者の方に問い合わせたところ質問の指摘通りとのことでした。