Diagnose shortest-path priorities and weights

Understand the likely causes

• Lazy priority updates intentionally leave obsolete entries behind. The current distance map, not every stored queue item, is authoritative.
• Dijkstra’s nonnegative-extension proof, Bellman-Ford’s source-reachability condition, and complete vertex representation are independent requirements. A successful heap operation does not validate them.

Freeze a tiny graph with a declared numeric domain

Record directed edges, all vertices including isolated ones, the source, and expected path costs. Verify every endpoint exists and weights belong to the accepted finite numeric domain. For this guide use exact integers so rounding and NaN do not obscure the diagnosis. A cheaper indirect path is essential to reproduce stale entries. Keep unreachable distinct from zero distance. A KeyError for a missing neighbor is malformed input, not a reason to change shortest-path theory or silently drop the edge. No external graph database is needed.

Compare stored priority with the authoritative distance

In a lazy Dijkstra implementation, an improvement inserts a fresh entry without removing the old one. On pop, skip an entry whose stored cost differs from the distance map. The program makes this ordinary event visible and never overwrites the map from a stale entry. If adding early exit at a target, preserve the nonnegative-weight precondition and the validity check before treating the popped result as settled. Tuple tie-breaking also needs comparable vertex labels or a separate counter. These protocol details are part of the implementation, not optional cosmetic cleanup.

import heapq
from math import inf

graph = {"A": [("B", 9), ("C", 2)], "B": [], "C": [("B", 3)]}
distance = {vertex: inf for vertex in graph}
distance["A"] = 0
heap, trace = [(0, "A")], []
while heap:
    cost, vertex = heapq.heappop(heap)
    status = "current" if cost == distance[vertex] else "stale"
    trace.append((vertex, cost, status))
    if status == "stale":
        continue
    for neighbor, weight in graph[vertex]:
        if cost + weight < distance[neighbor]:
            distance[neighbor] = cost + weight
            heapq.heappush(heap, (distance[neighbor], neighbor))
print(trace)
print(distance["B"])

[('A', 0, 'current'), ('C', 2, 'current'), ('B', 5, 'current'), ('B', 9, 'stale')]
5

Treat negative weights as an algorithm-selection question

If a negative edge is accepted, adding the stale-entry check does not repair Dijkstra’s settlement proof. Select an algorithm appropriate to the graph, such as Bellman-Ford for general source paths with negative edges and reachable-cycle detection. A reachable negative cycle can prevent a finite minimum for affected destinations. An unreachable negative cycle cannot appear on any source path and should not poison that source’s result. Keep cycle detection conditioned on finite source reachability. Do not replace infinity with zero to simplify arithmetic, since that invents paths into disconnected components.

Cross-check distances and any recovered path separately

On tiny nonnegative graphs, compare the repaired implementation with an independent Floyd-Warshall reference and Bellman-Ford. Add zero-weight edges, equal-cost alternatives, an isolated vertex, and the cost9-to5 improvement. Test negative-edge rejection separately from reachable and unreachable negative-cycle cases. If predecessor reconstruction is exposed, verify the recovered edges exist and their weights sum to the reported distance; equal-distance paths need not be unique. A plausible distance alone cannot prove a correct predecessor chain. Keep all fixtures bounded local data rather than running load against a graph service.

Keep it from recurring

• Keep weight assumptions and graph ownership beside the API. Treat the distance map as current authority, retain a stale-entry regression graph, and report the actual lazy-heap size bound rather than an indexed-heap claim.