Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Shortest routes: skip stale min-heap entries

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

Dijkstra's algorithm repeatedly settles the currently shortest tentative route when every edge weight is nonnegative. A standard min-heap does not update an existing entry in place. This version pushes a new (distance, depot) pair after an improvement and leaves the old pair in the heap. When an old pair surfaces, its distance differs from the best recorded distance and it is skipped. A predecessor map reconstructs one route after the destination is settled. The code validates every edge before searching, rejects unknown depots and negative travel times, and returns None if the destination is unreachable. It does not account for changing road times while a search runs.

Operational case

From D-19, a direct route to D-47 costs 14 minutes, but D-19 to D-26 costs 7 and D-26 to D-47 costs 3. The improved route makes the older heap entry for D-47 stale. Continuing through D-52 for 4 more minutes yields a 14-minute route: D-19, D-26, D-47, D-52. Searching from D-52 back to D-19 returns None because this directed graph has no reverse roads. Skipping stale entries avoids processing the old D-47 distance as if it were current. The first current pop of the destination is final only because all edge weights are nonnegative.

Working Python program

python
from heapq import heappop, heappush


def shortest_route(roads, origin, destination):
    if origin not in roads or destination not in roads:
        raise ValueError("unknown depot")
    for departures in roads.values():
        for neighbor, travel_minutes in departures:
            if neighbor not in roads or travel_minutes < 0:
                raise ValueError("unknown depot or negative travel time")

    best = {origin: 0}
    previous = {}
    pending = [(0, origin)]
    while pending:
        distance, depot = heappop(pending)
        if distance != best[depot]:
            continue
        if depot == destination:
            route = [depot]
            while route[-1] != origin:
                route.append(previous[route[-1]])
            return distance, list(reversed(route))
        for neighbor, travel_minutes in roads[depot]:
            candidate = distance + travel_minutes
            if candidate < best.get(neighbor, float("inf")):
                best[neighbor] = candidate
                previous[neighbor] = depot
                heappush(pending, (candidate, neighbor))
    return None


depot_roads = {
    "D-19": [("D-26", 7), ("D-47", 14)],
    "D-26": [("D-47", 3), ("D-52", 8)],
    "D-47": [("D-52", 4)],
    "D-52": [],
}
print(shortest_route(depot_roads, "D-19", "D-52"))
print(shortest_route(depot_roads, "D-52", "D-19"))

Output

Output
(14, ['D-19', 'D-26', 'D-47', 'D-52'])
None

Time, space, and tradeoff

With V depots and E directed roads, validation and graph storage are O(V + E). Every strict improvement can add one heap entry, so this lazy approach may hold O(E) pending entries and take O((V + E) log(V + E)) time in a conservative bound. Best distances and predecessors use O(V) space. An indexed heap can keep one active entry per depot and support decrease-key, trading a position map and more update bookkeeping for a smaller heap. Negative weights invalidate this algorithm's settlement rule; use a method designed for them instead. The displayed route is one optimum, not necessarily unique when costs tie.

Common Mistakes

  • Do not process a popped distance that no longer equals the best known distance.
  • Do not accept a negative road weight and still rely on Dijkstra's settled-node rule.
  • Do not infer an undirected reverse road from a directed adjacency entry.
  • Do not claim the lazy heap has only O(V) entries in its worst case.

Connected lessons

Apply this operation in the depot rollback project, then check the deletion and route quiz.

Expiry heaps: invalidate stale TTL records on replacement adds a related lifecycle choice.

Radix heaps: queue nondecreasing integer priorities adds another queue operation contract.

Kruskal reconstruction trees: answer route bottlenecks through merge ancestors adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details