ダイクストラ法のコード(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="")