已经找到便宜路线，为什么遇到负数后还不能提前结束？

"""Integer weighted directed graphs; guarded Dijkstra and Bellman-Ford."""
import heapq
import itertools
import json
import math


def validate(n, edges, source):
    if type(n) is not int or n < 1 or not 0 <= source < n:
        raise ValueError("invalid graph/source")
    for a, b, weight in edges:
        if not (0 <= a < n and 0 <= b < n) or type(weight) is not int:
            raise ValueError("integer weights and valid vertices required")


def unsafe_early_target(n, edges, source, target):
    """Deliberately lacks the nonnegative precondition; used only as counterexample."""
    adjacency = [[] for _ in range(n)]
    for a, b, weight in edges:
        adjacency[a].append((b, weight))
    best, queue, settled = [math.inf] * n, [(0, source)], set()
    best[source] = 0
    while queue:
        cost, vertex = heapq.heappop(queue)
        if vertex in settled:
            continue
        settled.add(vertex)
        if vertex == target:
            return cost
        for neighbor, weight in adjacency[vertex]:
            candidate = cost + weight
            if neighbor not in settled and candidate < best[neighbor]:
                best[neighbor] = candidate
                heapq.heappush(queue, (candidate, neighbor))
    return math.inf


def dijkstra_target(n, edges, source, target):
    validate(n, edges, source)
    if not 0 <= target < n or any(weight < 0 for _, _, weight in edges):
        raise ValueError("Dijkstra requires nonnegative weights and a valid target")
    return unsafe_early_target(n, edges, source, target)


def bellman_ford(n, edges, source):
    validate(n, edges, source)
    distance = [math.inf] * n
    distance[source] = 0
    for _ in range(n - 1):
        changed = False
        for a, b, weight in edges:
            if distance[a] != math.inf and distance[a] + weight < distance[b]:
                distance[b] = distance[a] + weight
                changed = True
        if not changed:
            break
    for a, b, weight in edges:
        if distance[a] != math.inf and distance[a] + weight < distance[b]:
            raise ValueError("negative cycle reachable from source")
    return distance


def enumerate_simple_paths(n, edges, source, target):
    adjacency = [[] for _ in range(n)]
    for a, b, weight in edges:
        adjacency[a].append((b, weight))

    def visit(vertex, visited):
        if vertex == target:
            return 0
        return min((weight + visit(neighbor, visited | {neighbor})
                    for neighbor, weight in adjacency[vertex] if neighbor not in visited),
                   default=math.inf)
    return visit(source, {source})


def main():
    example = [(0, 1, 2), (0, 2, 5), (2, 1, -10)]
    wrong = unsafe_early_target(3, example, 0, 1)
    correct = bellman_ford(3, example, 0)[1]
    assert (wrong, correct) == (2, -5)
    checks = 1
    try:
        dijkstra_target(3, example, 0, 1)
        raise AssertionError("negative edge accepted")
    except ValueError:
        checks += 1
    # All 64 three-vertex DAGs with each edge absent or weight -2, 0, 3.
    slots = [(0, 1), (0, 2), (1, 2)]
    for weights in itertools.product([None, -2, 0, 3], repeat=3):
        edges = [(a, b, w) for (a, b), w in zip(slots, weights) if w is not None]
        for source in range(3):
            distances = bellman_ford(3, edges, source)
            for target in range(3):
                expected = enumerate_simple_paths(3, edges, source, target)
                assert distances[target] == expected
                checks += 1
                if all(w >= 0 for _, _, w in edges):
                    assert dijkstra_target(3, edges, source, target) == expected
                    checks += 1
    try:
        bellman_ford(3, [(0, 1, 1), (1, 2, -2), (2, 1, 0)], 0)
        raise AssertionError("reachable negative cycle ignored")
    except ValueError:
        checks += 1
    unreachable = bellman_ford(4, [(0, 1, 2), (2, 3, -1), (3, 2, 0)], 0)
    assert unreachable == [0, 2, math.inf, math.inf]
    checks += 1
    # Adding the same positive number per edge changes routes of different lengths.
    original_costs, shifted_costs = [1, 0 + 0], [1 + 2, (0 + 2) + (0 + 2)]
    assert original_costs[1] < original_costs[0] and shifted_costs[0] < shifted_costs[1]
    checks += 1
    print(json.dumps({"checks_passed": checks, "unsafe_early_target": wrong,
                      "bellman_ford_target": correct, "guard_rejects_negative": True,
                      "DAGs_checked": 64, "unreachable_negative_cycle": [0, 2, None, None],
                      "original_direct_and_two_edge_costs": original_costs,
                      "after_adding_two_per_edge": shifted_costs,
                      "boundary": "integer directed graphs; no real route measurement"}, indent=2))


if __name__ == "__main__":
    main()