56159


単一始点最短経路問題で負の閉路がある場合、アルゴリズムとしてベルマンフォード法が適用され、負の閉路がない場合、ダイクストラ法が適用されますが、閉路でなくても辺の重みが負数の場合ダイクストラ法の出力が正しくない原因は何でしょうか。

以下のダイクストラ法の参考コードを辺の重みが非負数の場合と負数を含む場合で実行したところ、出力が変わりましたが、その理由がわかりません。

閉路でなくても、辺の重みが負数だとなぜダイクストラ法では、出力が正しく求められないのでしょうか。

[ダイクストラ法の参考コード](https://engineeringnote.hateblo.jp/entry/python/algorithm-and-
data-structures/dijkstra)  
出力(辺のコストが非負の場合)

[code]

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

辺のコストが非負の場合

[code]

    route = [
        [INF, 2, 3, INF, INF, INF],
        [2, INF, 4, 3, 5, INF],
        [3, 4, INF, 6, 4, INF],
        [INF, 3, 6, INF, 1, 5],
        [INF, 5, 4, 1, INF, 3],
        [INF, INF, INF, 5, 3, INF]]
    
[/code]

出力(辺のコストに負数を含む場合)

[code]

    $ python dijkstra.py
    visited to A.
    visited to B.
    visited to E.
    visited to D.
    visited to F.
    visited to C.
    #printなし、プログラムが終了しない
    
[/code]

辺のコストに負数を含む場合

[code]

    route = [
        [INF, 2, 3, INF, INF, INF],
        [2, INF, 4, 3, -5, INF],
        [3, 4, INF, 6, 4, INF],
        [INF, 3, 6, INF, 1, 5],
        [INF, 5, 4, 1, INF, 3],
        [INF, INF, INF, 5, 3, INF]]
    
[/code]

実行したプログラム（上記URLより引用)

[code]

    # dijkstra.py
    import sys
    
    INF         = 10000
    VISITED     = 1
    NOT_VISITED = 0
    
    route = [
        [INF, 2, 3, INF, INF, INF],
        [2, INF, 4, 3, 5, INF],
        [3, 4, INF, 6, 4, INF],
        [INF, 3, 6, INF, 1, 5],
        [INF, 5, 4, 1, INF, 3],
        [INF, INF, INF, 5, 3, 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]

**回答を受けてやったこと**  
負の辺がある場合のテストケースを実行した結果を求めました。  
しかし、ダイクストラ法は閉路がなくて出力は求められても、辺の重みが負数だとなぜダイクストラ法では、出力が正しく求められないのかまだ理解できていません。

[code]

    #負の辺があって閉路ではないケース
    route = [
        [INF, 5, 3, INF, 3, INF],
        [2, INF, 4, 3, -3, INF],
        [3, 4, INF, 6, 4, INF],
        [INF, 3, 6, INF, 1, 5],
        [INF, 5, 4, 1, INF, 3],
        [INF, INF, INF, 5, 3, INF]]
    
    
    #結果
    $ python dijkstra.py
    visited to A.
    visited to C.
    visited to E.
    visited to D.
    visited to B.
    visited to F.
    minimal cost is 6.
    optimum route is 'A->B->E->F'.
    
[/code]


CC BY-SA 4.0
2019-06-27T12:00:35.930
56143
2019-06-28T09:45:26.830
2019-06-28T05:41:19.220
question
python python3 アルゴリズム
ダイクストラ法における辺の重みの正負における出力のちがいについて


自分の理解ですと、負の閉路がある時点でそれは最短経路問題としては解けないことになります。(ぐるぐるまわると、無限に負の重みを稼げるから)

2度と同じ枝ないし頂点を通らないとした場合であっても、それは多分 NP 困難な問題になりそうだと思ってます。(要検証)

負の閉路がない、負の重みを持つ枝があるグラフ上で最短経路を求めるのがベルマンフォードで、負の重みがないグラフ上での最短経路を求めるのがダイクストラだという理解です。


CC BY-SA 4.0
2019-06-27T12:07:33.320
56144
2019-06-27T12:07:33.320
754
56143
answer


ダイクストラ法については詳しい解説が山ほどあるので、詳細まで踏み込みませんが、その手続きを簡単に説明するなら

[ _新たに最短経路が確定した頂点を見つけて、その頂点に隣接する頂点の最短経路を更新する_ ] という作業をすべての頂点の最短経路が確定するまで続ける

というものです。

サンプロコードでいうと

[code]

    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
    
        #ここが隣接する頂点の最短経路を更新する部分
        for i in range(size):
            if cost[i] > route[x][i] + cost[x]:
                cost[i] = route[x][i] + cost[x]
                before[i] = x
    
[/code]

このような感じです。

問題なのは最短経路が確定した頂点を見つける部分のコードで、見ての通り、まだ確定してない頂点からコストが最小の頂点を選んでいるだけです。それでなぜ最短距離が確定した頂点を見つけることができるのかといえば、証明は省きますが
**すべての辺が非負だから** です。

試しに最小値を更新する部分のコードを

[code]

    for i in range(size):
        if cost[i] > route[x][i] + cost[x]:
            cost[i] = route[x][i] + cost[x]
            before[i] = x
            if visit[i] == VISITED: #<-
                print("cost changed {}".format(chr(65+i)))
    
[/code]

と変えると、負の辺がある場合だけこのログが出力されます。つまり最短距離が確定してないのに、その頂点を使って更新し、しかも二度とつかわないように
VISITED のマークをつけてしまっていることになります。  
試しにさらにそのあとに

[code]

            if visit[i] == VISITED:
                print("cost changed {}".format(chr(65+i)))
                visit[i] = NOT_VISITED #<-
    
[/code]

と加えると、最小値が更新された場合、再び探索の対象となるので負の閉路がない限り正しい答えが出ます。(ただしダイクストラ法と比べると効率が悪い)

あと負の辺がある場合のテストケースは

[code]

    route = [
        [INF, 5, 3, INF, 3, INF],
        [2, INF, 4, 3, -3, INF],
        [3, 4, INF, 6, 4, INF],
        [INF, 3, 6, INF, 1, 5],
        [INF, 5, 4, 1, INF, 3],
        [INF, INF, INF, 5, 3, INF]]
    
[/code]

こちらを使ってみてください。今のバージョンは負の閉路があるので、いずれにしても答えは出ません。

\-------追記--------  
紙にでも書きつつ考えればおそらくわかると思います。6つもあると面倒ですが、これぐらいなら可能でしょう。

[code]

    route = [
        [INF,   1,  10, INF],
        [INF, INF, INF,   1],
        [INF, -10, INF, INF],
        [INF, INF, INF, INF]
    ]
    
[/code]

ちなみにA->C->B->Dが最短経路で、コストは1になります。


CC BY-SA 4.0
2019-06-27T17:58:48.290
56155
2019-06-28T09:45:26.830
2019-06-28T09:45:26.830
33033
33033
56143
answer


提示された負のコストを持つデータには、負となる閉路があります。

[code]

    route = [
        [INF, 2, 3, INF, INF, INF],
        [2, INF, 4, 3, -5, INF],
        [3, 4, INF, 6, 4, INF],
        [INF, 3, 6, INF, 1, 5],
        [INF, 5, 4, 1, INF, 3],
        [INF, INF, INF, 5, 3, INF]]
    
[/code]

[code]

    B->E: -5
    E->D: 1
    D->B: 3
    
[/code]

となっており、`B->E->D->B`と一周すると、コストが -1
になります。つまり、この閉路を回れば回るほどコストは下がっていくので、この閉路を永久に探索していくため、プログラムが終了しません。


CC BY-SA 4.0
2019-06-27T22:19:19.087
56159
2019-06-27T22:19:19.087
3605
56143
answer