py-11-dijkstra

# Dijkstra shortest paths (heapq)

Implement **`solution.py`** with:

```python
def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    ...
```

Compute the **shortest-path distance** from `start` to every reachable node in a
weighted **directed** graph.

- `graph[u]` is a list of `(v, weight)` edges from `u` to `v`. Weights are
  non-negative.
- Return a dict mapping each **reachable** node to its minimum total distance from
  `start`. `start` itself maps to `0.0`.
- **Unreachable nodes must be omitted** from the result (do not include them with
  `inf`).
- A node that appears only as an edge target (never as a key in `graph`) is a
  valid node with no outgoing edges.
- Use the standard library only — implement Dijkstra's algorithm with
  **`heapq`** as the priority queue. Do **not** use networkx or any third-party
  library here.

Example:

```python
g = {
    "a": [("b", 1.0), ("c", 4.0)],
    "b": [("c", 2.0), ("d", 5.0)],
    "c": [("d", 1.0)],
    "d": [],
}
dijkstra(g, "a")
# {"a": 0.0, "b": 1.0, "c": 3.0, "d": 4.0}

dijkstra({"a": [("b", 2.0)], "b": [], "island": [("a", 1.0)]}, "a")
# {"a": 0.0, "b": 2.0}   # "island" is unreachable from "a", omitted
```

import math

import pytest

from solution import dijkstra


def test_basic_multipath():
    g = {
        "a": [("b", 1.0), ("c", 4.0)],
        "b": [("c", 2.0), ("d", 5.0)],
        "c": [("d", 1.0)],
        "d": [],
    }
    out = dijkstra(g, "a")
    assert out == {"a": 0.0, "b": 1.0, "c": 3.0, "d": 4.0}


def test_start_distance_zero():
    g = {"a": [("b", 7.0)], "b": []}
    out = dijkstra(g, "a")
    assert out["a"] == 0.0


def test_unreachable_omitted():
    g = {"a": [("b", 2.0)], "b": [], "island": [("a", 1.0)]}
    out = dijkstra(g, "a")
    assert out == {"a": 0.0, "b": 2.0}
    assert "island" not in out


def test_chooses_cheaper_route():
    # direct a->c is 10, but a->b->c is 3
    g = {
        "a": [("b", 1.0), ("c", 10.0)],
        "b": [("c", 2.0)],
        "c": [],
    }
    out = dijkstra(g, "a")
    assert out["c"] == pytest.approx(3.0)


def test_single_node_no_edges():
    out = dijkstra({"a": []}, "a")
    assert out == {"a": 0.0}


def test_target_only_node_has_no_outgoing():
    # "z" is only an edge target, never a key
    g = {"a": [("z", 5.0)]}
    out = dijkstra(g, "a")
    assert out == {"a": 0.0, "z": 5.0}


def test_zero_weight_edges():
    g = {"a": [("b", 0.0)], "b": [("c", 0.0)], "c": []}
    out = dijkstra(g, "a")
    assert out == {"a": 0.0, "b": 0.0, "c": 0.0}


def test_larger_graph_relaxation():
    g = {
        "s": [("a", 4.0), ("b", 1.0)],
        "b": [("a", 2.0), ("c", 5.0)],
        "a": [("c", 1.0)],
        "c": [("t", 3.0)],
        "t": [],
    }
    out = dijkstra(g, "s")
    # s->b(1)->a(3)->c(4)->t(7)
    assert out["a"] == pytest.approx(3.0)
    assert out["c"] == pytest.approx(4.0)
    assert out["t"] == pytest.approx(7.0)
    assert all(math.isfinite(v) for v in out.values())

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```python
import heapq

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    # Dictionary to store the shortest distance to each reachable node.
    # Initialize with the start node at distance 0.0.
    dist = {start: 0.0}
    
    # Priority queue (min-heap) to store (distance, node) tuples.
    # We start by pushing the start node.
    pq = [(0.0, start)]
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        # If the popped distance is greater than the currently known shortest distance
        # to node u, it means we have already processed u with a better path.
        # We can skip this stale entry.
        if current_dist > dist[u]:
            continue
        
        # Explore neighbors of u.
        # Use .get(u, []) to handle cases where a node exists as a target
        # but has no outgoing edges defined in the graph dictionary.
        for v, weight in graph.get(u, []):
            new_dist = current_dist + weight
            
            # If v is not yet visited (not in dist) or we found a shorter path to v,
            # update the distance and push to the priority queue.
            if v not in dist or new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    return dist
```

The user wants a Python implementation of Dijkstra's algorithm using `heapq`.

Requirements:
1. Function signature: `def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:`
2. Graph is directed, weighted, non-negative weights.
3. Return dict of reachable nodes and their shortest distance from `start`.
4. `start` maps to `0.0`.
5. Unreachable nodes omitted.
6. Nodes can exist as targets without being keys in `graph`.
7. Use `heapq` from standard library.

Algorithm steps:
1. Initialize `dist` dictionary with `start` node having distance `0.0`. All other nodes effectively have infinity, but since we only track reachable ones, we can just use a dict or a default dict. Actually, standard Dijkstra usually initializes all known nodes to infinity, but here we don't know all nodes upfront easily (though we could collect them). However, the requirement says "Unreachable nodes must be omitted". So initializing a dict with `start: 0.0` and updating it as we find shorter paths is sufficient.
2. Initialize a priority queue (min-heap) with `(0.0, start)`.
3. While the heap is not empty:
    a. Pop the node `u` with the smallest distance `d`.
    b. If `d` is greater than the currently known shortest distance to `u` (if `u` is in `dist`), skip it (lazy deletion).
    c. For each neighbor `v` and weight `w` in `graph.get(u, [])`:
        i. Calculate `new_dist = d + w`.
        ii. If `v` is not in `dist` or `new_dist < dist[v]`:
            - Update `dist[v] = new_dist`.
            - Push `(new_dist, v)` to the heap.
4. Return `dist`.

Edge cases:
- `start` node not in `graph` keys? The problem says "A node that appears only as an edge target... is a valid node". If `start` is not in `graph` keys, it has no outgoing edges. The result should be `{"start": 0.0}`.
- Disconnected components.
- Cycles (handled by Dijkstra naturally with non-negative weights).

Let's write the code.

```python
import heapq

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    # Dictionary to store the shortest distance to each node
    dist = {start: 0.0}
    
    # Priority queue stores tuples of (distance, node)
    # Initialize with the start node
    pq = [(0.0, start)]
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        # If we popped a node with a distance greater than the known shortest distance,
        # it means we have already processed this node with a better path.
        # We can skip processing it again.
        if current_dist > dist.get(u, float('inf')):
            continue
        
        # Explore neighbors
        # Use .get(u, []) to handle nodes that are targets but not keys in graph
        for v, weight in graph.get(u, []):
            new_dist = current_dist + weight
            
            # If v is not visited yet or we found a shorter path to v
            if v not in dist or new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    return dist
```

Wait, checking the condition `if current_dist > dist.get(u, float('inf')):`.
If `u` is not in `dist`, `dist.get(u, float('inf'))` returns infinity. `current_dist` will be less than infinity, so it proceeds.
However, `u` is added to `dist` only when we push to `pq` (except for start).
Actually, `start` is in `dist`.
When we push `(new_dist, v)`, we update `dist[v]`.
So if we pop `(d, u)`, `u` must be in `dist` because we only push if we update `dist`.
Wait, strictly speaking:
1. `start` added to `dist` and `pq`.
2. Pop `(0, start)`. `0 <= dist[start]`. Process neighbors.
3. Neighbor `v`. `new_dist`. Update `dist[v]`. Push `(new_dist, v)`.
4. Later pop `(d, v)`. `v` is in `dist`.
So `dist.get(u, float('inf'))` is safe, but `u` will always be in `dist` if it was pushed.
Actually, if we update `dist[v]` multiple times before popping `v`, the heap contains multiple entries for `v`.
When we pop the first one (smallest distance), `current_dist == dist[v]`. We process.
When we pop a later one (larger distance), `current_dist > dist[v]`. We skip.
So the check `if current_dist > dist[u]: continue` is correct.

Let's double check the requirements.
- "Unreachable nodes must be omitted". My implementation only adds nodes to `dist` when reached. Correct.
- "start itself maps to 0.0". Correct.
- "A node that appears only as an edge target... is a valid node". Handled by `graph.get(u, [])`.

One small detail: `graph` type hint says `dict[str, list[tuple[str, float]]]`.
The implementation matches.

Let's refine the code slightly for clarity and robustness.

```python
import heapq

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    # Initialize distances with start node at 0.0
    # Other nodes are implicitly infinity until reached
    dist = {start: 0.0}
    
    # Priority queue: (distance, node)
    pq = [(0.0, start)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # If the popped distance is greater than the recorded shortest distance,
        # this entry is stale.
        if d > dist[u]:
            continue
        
        # Iterate over neighbors. Use .get() to handle nodes with no outgoing edges
        # defined in the graph dict keys.
        for v, weight in graph.get(u, []):
            new_dist = d + weight
            
            # If v is not in dist (unvisited) or we found a shorter path
            if v not in dist or new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    return dist
```

Wait, `if d > dist[u]` assumes `u` is in `dist`.
Is it possible `u` is not in `dist`?
We push `(new_dist, v)` only after setting `dist[v] = new_dist`.
We initialize `dist[start] = 0.0` and push `(0.0, start)`.
So yes, any `u` popped from `pq` must be in `dist`.
So `dist[u]` is safe.

Let's verify the example cases.
Example 1:
g = {"a": [("b", 1.0), ("c", 4.0)], "b": [("c", 2.0), ("d", 5.0)], "c": [("d", 1.0)], "d": []}
start = "a"
dist = {"a": 0.0}, pq = [(0.0, "a")]
Pop (0.0, "a"). Neighbors:
- "b": new
…[11976 chars elided]…
t be omitted".
If I have `graph = {"a": []}` and `start = "b"`.
`dist` starts as `{"b": 0.0}`.
`pq` pops `b`. `graph.get("b", [])` is `[]`.
Returns `{"b": 0.0}`.
Node `a` is not in result. Correct.

If `graph = {"a": [("b", 1.0)], "c": []}` and `start = "a"`.
`dist` starts `{"a": 0.0}`.
Pop `a`. Neighbor `b`. `dist` becomes `{"a": 0.0, "b": 1.0}`. Push `b`.
Pop `b`. No neighbors.
Returns `{"a": 0.0, "b": 1.0}`.
Node `c` is not in result. Correct.

The logic holds.

Final check on the provided signature.
`def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:`
Matches exactly.

I'm ready.

```python
import heapq

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    # Dictionary to store the shortest distance to each reachable node.
    # Initialize with the start node at distance 0.0.
    dist = {start: 0.0}
    
    # Priority queue (min-heap) to store (distance, node) tuples.
    # We start by pushing the start node.
    pq = [(0.0, start)]
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        # If the popped distance is greater than the currently known shortest distance
        # to node u, it means we have already processed u with a better path.
        # We can skip this stale entry.
        if current_dist > dist[u]:
            continue
        
        # Explore neighbors of u.
        # Use .get(u, []) to handle cases where a node exists as a target
        # but has no outgoing edges defined in the graph dictionary.
        for v, weight in graph.get(u, []):
            new_dist = current_dist + weight
            
            # If v is not yet visited (not in dist) or we found a shorter path to v,
            # update the distance and push to the priority queue.
            if v not in dist or new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    return dist
```
This is the content of `solution.py`.

I will output the code block now.