0

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

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

$ 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'.
# 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="")

2 件の回答 2

2

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

1

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

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

# 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を以下のようにすれば良いでしょう。

    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 # この行を追加

この質問に回答するには、ログインする必要があります。