ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される

ダイクストラ法のコード(python)を参考に以下のプログラムを実行しました。
出力として最短ルートは'A->C->B->D'と求められましたが、コストは「5+(-4)+1=２」になるところ、'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="")