56233


[ダイクストラ法のコード(python)](https://engineeringnote.hateblo.jp/entry/python/algorithm-
and-data-structures/dijkstra)を参考に以下のプログラムを実行しました。  
出力として最短ルートは'A->C->B->D'と求められましたが、コストは「5+(-4)+1=２」になるところ、'A->B->D'の「3+1=4」が出力されました。原因がわからないです。

グラフ部分はコードのrouteにあたります。  
出力

[code]

    $ python dijkstra.py
    visited to A.
    visited to B.
    visited to D.
    visited to C.
    minimal cost is 4.
    optimum route is 'A->C->B->D'.
    
[/code]

[code]

    # dijkstra.py
    import sys
    
    INF         = 10000
    VISITED     = 1
    NOT_VISITED = 0
    
    route = [
        [INF,   3,  5, INF],
        [INF, INF, INF,   1],
        [INF, -4, INF, INF],
        [INF, INF, INF, INF]
    ]
    
    size = len(route)
    cost = [INF for _ in range(size)]
    visit = [NOT_VISITED for _ in range(size)]
    before = [None for _ in range(size)]
    cost[0] = 0
    while True:
        min = INF
        for i in range(size):
            if visit[i] == NOT_VISITED and cost[i] < min:
                x = i
                min = cost[x]
        if min == INF:
            break
        visit[x] = VISITED
        print("visited to {}.".format(chr(65+x)))
    
        for i in range(size):
            if cost[i] > route[x][i] + cost[x]:
                cost[i] = route[x][i] + cost[x]
                before[i] = x
    
    if cost[size-1] == INF:
        print("could not find optimum route.")
        sys.exit(1)
    
    i = size - 1
    optimum_route = []
    while True:
        optimum_route.insert(0, chr(65+i))
        if i == 0:
            break
        i = before[i]
    
    print("minimal cost is {}.".format(cost[size-1]))
    print("optimum route is '", end="")
    for i in range(len(optimum_route)):
        print(optimum_route[i], end="")
        if i == len(optimum_route) -1:
            print("'.")
            break
        print("->", end="")
    
[/code]


CC BY-SA 4.0
2019-06-29T12:11:03.120
56230
2019-06-29T18:02:06.500
question
python python3 アルゴリズム データ構造 グラフ理論
ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される


一言でいうと、このプログラムは、すべての辺が正であることを仮定したアルゴリズムを使っているため、うまく動きません。以下は、プログラムの`while`ループを抜き出したものです。説明のために`#
for ループ 1`と`# for ループ 2`というコメントを入れています。

[code]

    while True:
        min = INF
    
        # for ループ 1
        for i in range(size):
            if visit[i] == NOT_VISITED and cost[i] < min:
                x = i
                min = cost[x]
        if min == INF:
            break
        visit[x] = VISITED
        print("visited to {}.".format(chr(65+x)))
    
        # for ループ 2
        for i in range(size):
            if cost[i] > route[x][i] + cost[x]:
                cost[i] = route[x][i] + cost[x]
                before[i] = x
                visit[i] = NOT_VISITED
    
[/code]

`# for ループ
1`直後の`for`で何をしているかというと、まだAからの距離が確定していない(`NOT_VISITED`)ノードのうち、一番距離が短いものを取り出しています。

例えば、`while`の一周目が終わった時点のコストは、`A==0, B==3, C==5,
D==INF`となっています。Aのコストが一番小さいですが、一周目で既にAは`VISITED`になっているので、二回目の`# for ループ
1`で選ばれるのは、Bになります。この後、Bを`VISITED`と確定し、更にBのコストを元にして、Bから繋がったノードのコストを計算します。

さて、経路のコストがすべて正の場合は、ここでBを`VISITED`と確定してしまって構いません。CからBに行く経路があるかもしれませんが、Cのコストが既に5であるため、C経由でBに行く経路のコストは、すべて5より大きくなるからです。

しかし今回の場合は負の経路があります。したがって、C経由でBに行く経路で、コストが小さいものがありえます。実際、`C->B`のコストは-4なので、`A->C->B`は1となり、コストが小さくなっています。

Bの新しいコストが見つかったので、B以降のコストもすべて再計算しなければなりませんが、すでにBを`VISITED`としてしまっているため、再計算されません。したがって、Dのコストは古いまま、つまり`A->B->D`の4になるわけです。

最短ルートが正しいのは、`B->D`の経路は一通りしかないため、再計算しなくても同じだから、つまり、たまたま正しくなっているだけです。

変更を最小限にして、正しい結果を求めるには、新しいコストが見つかったときに、`VISITED`だったノードを`NOT_VISITED`に戻せばいいです。`#
for ループ 2`の後の`for`を以下のようにすれば良いでしょう。

[code]

        for i in range(size):
            if cost[i] > route[x][i] + cost[x]:
                cost[i] = route[x][i] + cost[x]
                before[i] = x
                visit[i] = NOT_VISITED # この行を追加
    
[/code]


CC BY-SA 4.0
2019-06-29T17:57:09.760
56233
2019-06-29T17:57:09.760
3605
56230
answer


ダイクストラ法では前提として「コストが負ではない」というものを仮定してます。  
ルートが正しく表示されているのは偶然ですね。  
例えば与えられたグラフにA->Dのコスト3の辺を追加するとコストもルートも共に間違ったもの(A->D:cost=3)が出力されます。（求めたいのは元のA->C->B->D:cost=2のまま）


CC BY-SA 4.0
2019-06-29T18:02:06.500
56234
2019-06-29T18:02:06.500
17106
56230
answer