Using Dijkstra’s algorithm with a priority queue efficiently

Dijkstra’s algorithm finds a shortest path in a weighted graph when every edge cost is non-negative. For a route, an edge might represent a road segment and its cost might be kilometres, travel minutes or a carefully defined combination of distance and tolls. The decisive implementation choice is to keep the smallest tentative distance at the front of a min-priority queue, rather than repeatedly scanning every unvisited vertex. In Python, the standard library’s heapq provides that queue without an external dependency.

Correctness and speed come from matching the weight to the question. A fixed-distance graph answers which route is physically shortest; a time-weighted graph answers which route should arrive soonest. Those are different optimisation problems, especially when traffic, timetables or tolls vary. The implementation below uses a binary heap, relaxes neighbouring edges, rejects stale heap entries and can stop as soon as the target is removed with its current best distance.

Why the priority queue matters

At each step, Dijkstra needs the unvisited vertex with the smallest tentative distance. A linear scan for that vertex leads to quadratic behaviour on dense graphs. A binary min-heap supports insertion and removal in logarithmic time, so an adjacency-list implementation on a simple graph normally achieves (O((V+E)\log V)) time and (O(V+E)) space. Here, (V) is the number of vertices and (E) is the number of directed edges.

The most common Python approach is lazy deletion. When a shorter route to a vertex is discovered, another candidate is pushed into the heap instead of searching existing entries to change them. The old entry remains until it reaches the top, where a comparison with the best-known distance identifies it as stale. This avoids implementing decrease-key and is usually simpler, although a graph with many parallel edges can make the heap larger than (V).

A compact implementation relies on four connected pieces:

• An adjacency list mapping each vertex to its outgoing (neighbour, weight) pairs.
• A distance dictionary storing the cheapest distance discovered so far.
• A heap containing (distance, vertex) candidates ordered by distance.
• A predecessor dictionary recording where each improved path came from.

Heap entries must be comparable. If vertex identifiers have mixed types, use a monotonically increasing counter as the second tuple field and keep the identifier third, preventing the interpreter from comparing unlike identifiers when distances tie.

Modelling routes as weighted graphs

A route graph needs precise semantics. Intersections, stations or delivery stops can be vertices; traversable connections become edges. In an undirected model, both directions receive the same weight. A directed model suits one-way streets, service loops or walking paths permitted in only one direction. Edge weights must stay non-negative, and every weight in one run should represent the same quantity, whether that is metres, minutes, dollars or a carefully defined weighted combination.

Real Australian networks make those distinctions visible. Sydney and Melbourne contain harbour crossings, tunnels, ring roads and dense one-way street systems, while drivers keep to the left. Australian road rules also set a default 50 km/h limit in built-up areas unless signs state otherwise. Using that rule as a rough travel-time estimate can be misleading near schools and major intersections, so signed limits and observed conditions are better inputs.

Not every graph problem is a shortest-path problem. If the goal is to order dependent tasks, a directed acyclic graph may be the better model, and the topological sorting tutorial explains how to process such dependencies. For routing, disconnected components should remain explicit rather than receiving invented zero-cost edges, because those false connections can make an unreachable destination appear reachable.

Implementing the search in Python

The Python version below expects a dictionary of adjacency lists. It validates weights before searching, maintains predecessor links and optionally stops when the target is settled. A tuple such as (0, "Central Station") represents a candidate distance and the vertex reached by that path.

from heapq import heappop, heappush
from math import inf


def dijkstra(graph, source, target=None):
    for edges in graph.values():
        for _, weight in edges:
            if weight < 0:
                raise ValueError(
                    "Dijkstra requires non-negative edge weights"
                )

    best = {source: 0}
    previous = {}
    heap = [(0, source)]

    while heap:
        distance, node = heappop(heap)

        # Ignore an entry superseded by a shorter path.
        if distance != best.get(node):
            continue

        # The target is final only after its current entry is popped.
        if target is not None and node == target:
            break

        for neighbour, weight in graph.get(node, []):
            candidate = distance + weight

            # Relax the edge if it produces a better distance.
            if candidate < best.get(neighbour, inf):
                best[neighbour] = candidate
                previous[neighbour] = node
                heappush(heap, (candidate, neighbour))

    return best, previous


def build_path(previous, source, target):
    if target == source:
        return [source]
    if target not in previous:
        return None

    path = [target]
    while path[-1] != source:
        path.append(previous[path[-1]])

    return list(reversed(path))

Each loop removes the smallest candidate. If its stored distance differs from the best known for that vertex, it is stale and is ignored. Otherwise, the algorithm relaxes every outgoing edge: it computes a possible new distance, and a smaller result updates both the distance table and predecessor. The optional target check is placed after the stale-entry check, which prevents an obsolete heap entry from ending the search too early.

After the loop, best contains the final distance for the target and tentative distances for other reached vertices when an early exit occurred. previous supports path reconstruction, producing a partial shortest-path tree when the search stops early. After a complete run, those predecessor links form a shortest-path tree rooted at the source. If a target is unreachable, it will not appear in best; build_path returns None rather than raising a misleading KeyError.

Preserving correctness while improving speed

Dijkstra’s correctness rests on the non-negative-weight rule. Once a vertex is removed from the heap with its current best distance, no later path can improve it, because every additional edge has a cost of zero or more. Negative edge weights break that argument; use Bellman–Ford when negative weights are unavoidable. Zero-weight edges are valid and are common in models where moving between platform levels has no added distance.

Several checks keep an implementation trustworthy:

• Validate every edge before the target can trigger an early exit.
• Keep weights in one unit and avoid mixing metres with seconds accidentally.
• Ignore stale heap entries before checking for the target.
• Store predecessor links whenever a distance strictly improves.

Time-dependent costs require care. If an edge’s cost changes with arrival time, Dijkstra is suitable only when the cost obeys the FIFO property: leaving later cannot produce an earlier arrival than leaving earlier. Otherwise, the algorithm may settle a vertex too soon. A time-dependent edge can otherwise be represented by a function from departure time to arrival time, provided that ordering condition is preserved.

Extending shortest paths to real journeys

A graph weighted by distance answers only one operational question. Delivery planners may prefer a slightly longer route that avoids a toll, a truck restriction or heavy traffic. Representing that preference as an edge cost makes the optimisation explicit, but combining incompatible measures in one number can hide trade-offs. Separate runs for distance, travel time and monetary cost are often clearer than a single blended weight.

Public transport adds transfer waiting, walk time and timetables. In Melbourne, a passenger may combine a Myki trip on a tram, rail or bus with a walk; in Sydney, an Opal-based journey can connect train, light rail, bus and ferry. A graph can represent stations and walking links, while scheduled edges carry waiting or in-vehicle times. If passengers may wait, edge functions must still preserve the FIFO condition.

Some dynamic workloads also need faster range queries over distance or edge arrays. A segment tree can maintain minima across changing intervals, and the segment tree guide explains that structure. It is complementary rather than a replacement for the heap: Dijkstra manages the frontier of candidate vertices, while a segment tree answers a specific range query. Use it only when those queries dominate the workload.

Applying the method across Australia

At Australian scale, the same pattern supports journey planners, warehouse routing and supermarket delivery networks serving Coles and Woolworths. Delivery vehicles leave depots, visit stores or homes and return, so the graph may include time windows, vehicle capacity and unloading duration. A plain shortest path gives the baseline; constraints often require additional heuristics or a different algorithm.

Graph construction can dominate runtime when the data arrives as records rather than hand-written edges. For example, a pandas and Arrow pipeline can clean source and destination fields, normalise identifiers and produce grouped edge tables before conversion to adjacency lists. Columnar processing is particularly useful for large extracts, although the Dijkstra frontier remains a small mutable heap rather than a table that benefits from columnar storage.

Precise location histories require care under the Privacy Act 1988 (Cth), which can apply when location information is about an identifiable person. Australian transport operators and delivery firms should minimise collection, secure access and explain how movement data is used. From an algorithmic standpoint, that means anonymous road segments may be enough: store edge identifiers and costs rather than retaining every journey trace. The efficient design is then both privacy-aware and computationally lean.