The task is to return the length of a cheapest path in a directed graph with nonnegative edge weights. A breadth first search counts edges and would only be correct when all weights were equal, so I will use Dijkstra's algorithm. The graph is supplied as a mapping from each vertex to an iterable of (neighbor, weight) pairs. A vertex that occurs only as a neighbor has no outgoing edges unless it also appears as a key. The answer is None when the target is unreachable.

The priority queue stores tentative distances. When the smallest stored distance is removed, it gives the next candidate to finalize. The nonnegative weight requirement is essential: extending a path cannot produce a cheaper prefix than the one already removed. Without that property, reaching the target once would not certify optimality, and a later negative edge could invalidate the result. I will check weights before beginning so that early termination at the target does not skip a negative edge elsewhere in the supplied graph.

A Python heap does not have a convenient decrease-key operation. Instead, a better path pushes another heap entry, and the old entry remains until it is removed. At removal, an entry whose distance differs from the best known distance is stale and can be ignored. This is more than a performance detail: processing stale entries can multiply work and make it harder to explain why the algorithm is efficient, even though relaxing from them would usually leave the final distances unchanged.

There is a subtle issue when vertex objects are not comparable. A heap of (distance, vertex) pairs compares vertices when distances tie, which raises an exception for unrelated objects. The queue therefore uses (distance, counter, vertex). The counter is strictly increasing and unique, so it resolves equal-distance ordering before Python needs to compare vertex objects. The counter has no meaning in the graph; it is only a stable way to represent queue entries safely.

I also need to materialize each adjacency iterable. Validation consumes generators, and then traversal would see an empty generator if I tried to read it a second time. Building a fresh adjacency dictionary once gives the validator and the search the same edges. This does not change the caller's graph, and it lets the function support an input containing generator-valued adjacency lists. The cost is O(E) additional storage, which is reasonable for this general input contract.

Zero-weight edges are allowed. They can create a cycle with no additional cost, but the strict relaxation check prevents an endless sequence of equal-distance pushes. Parallel edges are allowed too: a more expensive edge may put an initial candidate in the queue, and a cheaper parallel edge may immediately replace its distance. The stale-entry check handles the older candidate later. An isolated source equal to the target should return zero, because the empty path is valid even when the graph has no keys.

Here is the code. The comments focus on why each queue transition is justified and on the properties that would be lost if the comparisons were changed.

For the example, the direct route to middle costs eight, but the detour discovers a cost of three before that older queue entry is used. Middle then produces a finish distance of six. The direct detour-to-finish edge proposes twelve, which cannot replace six. The old middle entry at eight eventually becomes irrelevant, and the target is returned at six. Searching for missing exhausts all reachable queue entries and returns None; it does not confuse an absent target with a zero-cost route.

For correctness, assume a fresh queue entry for u has minimum distance d. If there were a cheaper path to u, follow that path from the source and locate the first vertex not yet finalized. Its predecessor was finalized earlier and would have relaxed the crossing edge. The tentative distance at that crossing vertex would be no more than the cheaper path's total cost, since all remaining weights are nonnegative. It would therefore have been removed before d, contradicting the choice of u. This is the greedy argument that permits the immediate return when u is the target.

The proof depends on considering only fresh entries. A stale entry certifies an older discovered path, and the dictionary already contains evidence of something better. Skipping it does not remove the better entry from the heap, because every strict improvement is pushed at the moment it is recorded. Eventually either that better entry is removed, or an even better entry replaces it and carries the same responsibility. Thus each best known distance always has a corresponding pending candidate until it is processed.

One might store an explicit finalized set as well. It is unnecessary here because a fresh removal cannot later be improved under the nonnegative premise. All relaxations are strict, so an equal route cannot enqueue another fresh copy either. The distance dictionary plus the stale check already express the relevant invariant. This keeps the implementation short while preserving the ability to explain exactly which entries may be ignored.

I want to walk through the queue state in more detail, because the first discovery of a target is a tempting place to return and that would be incorrect. Suppose start has an edge directly to finish with weight nine and an edge to bridge with weight two. Bridge has an edge to finish with weight one. Discovering finish from start merely establishes an upper bound of nine. The queue still contains bridge at two, and processing bridge improves finish to three. The correct stopping event is removal of a fresh finish entry from the minimum queue, rather than insertion of any finish entry.

That distinction also explains why an ordinary visited set can be used incorrectly. Marking a node visited as soon as it is inserted would prevent bridge from improving the earlier finish candidate. A visited set is valid only when its members are finalized on removal. This implementation avoids that separate state entirely, but it does not avoid the underlying timing requirement. The stale comparison is performed before the target comparison, so an old finish entry cannot cause a premature return if it happens to be removed after an improvement.

But wait, could the strict relaxation check miss a useful path with the same distance but a different route? It could omit that route, but the requested value is only the minimum distance. Two equal-cost routes have the same relevance to every outgoing edge because extending either with the same edge adds the same weight. There is no path-dependent state such as a limit on stops or a forbidden set of previously used vertices. If such state were part of the task, node identity alone would no longer be an adequate search state. Under the present contract, keeping one best distance per vertex is sufficient.

The source-equals-target case deserves a similar distinction between graph structure and path definition. The empty path has cost zero, so returning zero is correct even if there is a positive cycle back to source. With nonnegative weights, no nonempty route can improve on zero. A zero-weight cycle ties it but still does not change the answer. The initial queue entry is fresh and passes the target comparison immediately. Validation still happens first, because this function promises to reject a supplied negative edge even when the requested path would not traverse it.

That validation choice is intentional rather than necessary to the mathematical proof for a particular reachable component. An alternative interface might validate only edges encountered from source and ignore an unreachable negative component. Both interfaces can be defined, but they would produce different behavior for the same malformed input. Copying and validating the supplied adjacency mapping before search gives one clear rule: all supplied weights meet the stated requirement, or the function raises. It also means that malformed edge pairs are rejected by ordinary tuple unpacking before any result is returned.

What about a destination that appears nowhere in the graph? There is no special membership check at the beginning. If it equals source, the empty path supplies the answer. Otherwise it can only become reachable through an edge, and an edge mentioning it would make it appear as a neighbor. If no such discovery occurs, queue exhaustion yields None. This behavior is more general than demanding that both endpoints be dictionary keys, because a terminal vertex often has no explicit adjacency entry. Treating a missing list as empty gives those vertices their natural graph meaning.

I should also verify the treatment of repeated neighbors. Imagine two outgoing edges from a node to the same neighbor, one with weight seven and another with weight four. If the expensive edge is encountered first, it pushes a tentative distance that the cheaper edge then improves. If the cheap edge is encountered first, the expensive edge fails the strict comparison and does not push. Either order yields the same best distance. The heap contents can differ temporarily, but the stale check removes that representation difference before it affects traversal or the returned result.

Self-edges behave in the same way. A positive self-edge proposes a larger distance than the node already has and is ignored. A zero-weight self-edge proposes equality and is ignored too. No explicit self-edge filter is needed. The nonnegative constraint rules out the case that would continually improve the source through a negative self-edge. Keeping these cases in the ordinary relaxation logic is simpler than adding branches whose only purpose would be to restate consequences of the main comparison.

For vertex objects, the dictionary still requires hashability and equality, even though the heap counter removes the need for ordering. These are different requirements. A list cannot be a vertex under this mapping-based representation because it is unhashable, while an arbitrary hashable object can be one without implementing less-than. The sequence counter is unique across pushes in a single call. It starts fresh on each invocation, so calls do not share ordering state or retain references to vertices from earlier searches.

The copied adjacency lists also isolate the traversal from one particular kind of caller surprise. A generator is exhausted exactly once during materialization, and its yielded edges become an ordinary list. The algorithm then traverses that list whenever its vertex is finalized. It does not repeatedly ask the generator to reproduce edges. This is not a promise of safety against concurrent mutation of the original vertex objects themselves; it simply avoids changing or consuming the caller's adjacency iterables during the later heap loop. For normal immutable labels and numeric weights, that is the useful ownership guarantee.

Let me re-check the complexity claim against a graph with many parallel edges, since writing log V carelessly can conceal an assumption. There can be more than V squared edge records in a multigraph, and a sequence of decreasing parallel-edge weights may push many tentative entries. The heap size is therefore bounded in terms of E, not solely V. The more explicit logarithm of E plus one covers that representation. In an ordinary simple graph, E is bounded by V squared, so log E is O(log V) when the graph has enough edges for the distinction to matter.

The example harness deliberately prints a few contrasting results instead of embedding a large grid of almost identical checks. The finish query demonstrates an improvement after initial discovery, the source query demonstrates the empty path, and the missing query demonstrates exhaustion. The middle-to-detour edge of weight zero exercises the strict improvement rule without creating extra candidates at the same cost. Together those transitions are enough to make the implementation's state changes inspectable in a short run. More random cases could compare against a slower reference, but that belongs in a test suite rather than in the answer's example harness.

Validation and copying take O(V + E) time and storage. The heap may contain O(E) entries over the search, giving O((V + E) log(E + 1)) time in this straightforward implementation, with O(V + E) space including the copied graph. For a simple graph, this is commonly written O((V + E) log V). No path reconstruction is requested, so storing predecessors would add state without contributing to the result. The final function returns the cheapest distance only.

```python
from heapq import heappop, heappush
from itertools import count


def shortest_distance(graph, source, target):
    """Return a cheapest nonnegative path cost, or None if unreachable."""
    adjacency = {node: list(edges) for node, edges in graph.items()}
    for edges in adjacency.values():
        for neighbor, weight in edges:
            if weight < 0:
                raise ValueError("Dijkstra requires nonnegative weights")

    # distance records the best discovered path, rather than the number of
    # hops or the first path encountered. The initial zero corresponds to
    # the empty source-to-source path, which remains valid even if source
    # has no adjacency entry. The extra queue field avoids comparing nodes.
    distance = {source: 0}
    sequence = count()
    queue = [(0, next(sequence), source)]
    while queue:
        current, _, node = heappop(queue)
        # A shorter path may have been discovered after this entry was
        # queued. Only the entry agreeing with the current best distance
        # can finalize the vertex. Discarding the older one also prevents
        # redundant traversals of a potentially large adjacency list.
        if current != distance[node]:
            continue
        if node == target:
            return current
        for neighbor, weight in adjacency.get(node, ()):
            candidate = current + weight
            # Equality cannot improve a shortest distance. Using a strict
            # comparison is especially useful for zero-weight cycles:
            # traversing such a cycle never creates another queue entry.
            # Missing neighbors have no discovered distance yet, so their
            # first path is accepted without manufacturing a finite bound.
            if neighbor not in distance or candidate < distance[neighbor]:
                distance[neighbor] = candidate
                heappush(queue, (candidate, next(sequence), neighbor))
    return None


if __name__ == "__main__":
    graph = {
        "start": [("middle", 8), ("detour", 2)],
        "detour": [("middle", 1), ("finish", 10)],
        "middle": [("finish", 3), ("detour", 0)],
    }
    for destination in ("finish", "start", "missing"):
        print(destination, shortest_distance(graph, "start", destination))
```
