ダイクストラ法における辺の重みの正負における出力のちがいについて
単一始点最短経路問題で負の閉路がある場合、アルゴリズムとしてベルマンフォード法が適用され、負の閉路がない場合、ダイクストラ法が適用されますが、閉路でなくても辺の重みが負数の場合ダイクストラ法の出力が正しくない原因は何でしょうか。
以下のダイクストラ法の参考コードを辺の重みが非負数の場合と負数を含む場合で実行したところ、出力が変わりましたが、その理由がわかりません。
閉路でなくても、辺の重みが負数だとなぜダイクストラ法では、出力が正しく求められないのでしょうか。
ダイクストラ法の参考コード
出力(辺のコストが非負の場合)
$ 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'.
辺のコストが非負の場合
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]]
出力(辺のコストに負数を含む場合)
$ python dijkstra.py
visited to A.
visited to B.
visited to E.
visited to D.
visited to F.
visited to C.
#printなし、プログラムが終了しない
辺のコストに負数を含む場合
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]]
実行したプログラム(上記URLより引用)
# 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="")
回答を受けてやったこと
負の辺がある場合のテストケースを実行した結果を求めました。
しかし、ダイクストラ法は閉路がなくて出力は求められても、辺の重みが負数だとなぜダイクストラ法では、出力が正しく求められないのかまだ理解できていません。
#負の辺があって閉路ではないケース
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'.