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]:
    dist = {start: 0.0}
    pq = [(0.0, start)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
            
        for v, w in graph.get(u, []):
            new_dist = d + w
            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 an implementation of Dijkstra's algorithm in Python using `heapq`.
The function signature is:
```python
def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
```

Key requirements:
- Directed graph with non-negative weights.
- Return a dict mapping reachable nodes to their shortest distance from `start`.
- `start` maps to `0.0`.
- Unreachable nodes are omitted.
- Nodes can appear only as targets (not keys in `graph`).
- Use `heapq` for the priority queue.
- Standard library only.

Algorithm:
1. Initialize `dist` dictionary with `start: 0.0`.
2. Initialize a priority queue `pq` with `(0.0, start)`.
3. While `pq` is not empty:
   a. Pop the node `u` with the smallest distance `d`.
   b. If `d > dist[u]`, continue (stale entry).
   c. For each neighbor `v` and weight `w` in `graph.get(u, [])`:
      i. Calculate `new_dist = d + w`.
      ii. If `v` not in `dist` or `new_dist < dist[v]`:
          - Update `dist[v] = new_dist`.
          - Push `(new_dist, v)` to `pq`.
4. Return `dist`.

Wait, `graph` might not contain all nodes as keys. So `graph.get(u, [])` is correct.
Also, nodes that are only targets will be added to `dist` when reached, and since they aren't keys in `graph`, `graph.get(v, [])` will return `[]`, which is correct.

Let's trace the example:
`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` (1.0), `c` (4.0).
`dist["b"] = 1.0`, push `(1.0, "b")`
`dist["c"] = 4.0`, push `(4.0, "c")`
Pop `(1.0, "b")`. Neighbors: `c` (2.0), `d` (5.0).
`new_dist_c = 1.0 + 2.0 = 3.0 < 4.0`. `dist["c"] = 3.0`, push `(3.0, "c")`
`dist["d"] = 1.0 + 5.0 = 6.0`, push `(6.0, "d")`
Pop `(3.0, "c")`. Neighbors: `d` (1.0).
`new_dist_d = 3.0 + 1.0 = 4.0 < 6.0`. `dist["d"] = 4.0`, push `(4.0, "d")`
Pop `(4.0, "d")`. Neighbors: `[]`.
Pop `(4.0, "c")` (stale, `4.0 > 3.0`), skip.
Pop `(6.0, "d")` (stale, `6.0 > 4.0`), skip.
Result: `{"a": 0.0, "b": 1.0, "c": 3.0, "d": 4.0}`. Matches example.

Second example:
`{"a": [("b", 2.0)], "b": [], "island": [("a", 1.0)]}`, start `"a"`
`dist = {"a": 0.0}`, `pq = [(0.0, "a")]`
Pop `"a"`, neighbor `"b"` (2.0). `dist["b"] = 2.0`, push `(2.0, "b")`.
Pop `"b"`, neighbors `[]`.
Result: `{"a": 0.0, "b": 2.0}`. Matches example.

Edge cases:
- `start` not in `graph`? The problem says `graph[u]` is a list... but if `start` is not a key, `graph.get(start, [])` returns `[]`, so it just returns `{"start": 0.0}`. That's correct.
- Disconnected components: handled correctly, only reachable nodes in `dist`.
- Weights are non-negative: Dijkstra works.
- `heapq` usage: standard.

Implementation details:
```python
import heapq

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    dist = {start: 0.0}
    pq = [(0.0, start)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
            
        for v, w in graph.get(u, []):
            new_dist = d + w
            if v not in dist or new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    return dist
```

Wait, should I import `heapq` inside the function or at the top? The prompt says "Implement `solution.py` with: ...". I'll put `import heapq` at the top.

Check types: `graph: dict[str, list[tuple[str, float]]]`, `start: str`, returns `dict[str, float]`.
The code matches.

One minor point: `graph.get(u, [])` works fine.
Is there any case where `start` is not in `graph` but has outgoing edges? The problem says `graph[u]` is a list of edges from `u`. If `start` is not a key, it has no outgoing edges. That's consistent.

What about floating point precision? The problem uses floats, standard Dijkstra handles it. No special requirements.

Let's double check the exact signature requested:
```python
def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    ...
```

I will provide the full code for `solution.py`.

One thing: `heapq` is standard library, so `import heapq` is fine.

Code structure:
```python
import heapq

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    dist = {start: 0.0}
    pq = [(0.0, start)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
            
        for v, w in graph.get(u, []):
            new_dist = d + w
            if v not in dist or new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    return dist
```

Wait, should I consider that `graph` might contain nodes that are not reachable? The problem says "Unreachable nodes must be omitted from the result". My code only adds nodes to `dist` when they are reached, so unreachable nodes are naturally omitted. This matches the requirement.

Is there any issue with `d > dist[u]` when `u` is not in `dist`? `u` is always in `dist` because we only push to `pq` after adding to `dist`, and we start with `start` in `dist`. So `dist[u]` is safe.

One minor optimization/cleanliness: `graph.get(u, [])` is correct.
The code looks solid.

I will output the solution as requested.
No extra prose.
Fenced code block with `solution.py`.
Check signature matches exactly.
All good.
Proceed. 
Let's quickly verify type hints compatibility. Python 3.9+ supports `dict[str, ...]`. The prompt uses it, so it's fine.
I'll wrap it in the requested format.
Done. 
Output matches response. 
One detail: `import heapq` should be at the top of the file.
The prompt says "Implement `solution.py` with: ...". I will provide the full file content.
All set. 
Output generation. 
```python
import heapq

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    dist = {start: 0.0}
    pq = [(0.0, start)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
            
        for v, w in graph.get(u, []):
            new_dist = d + w
            if v not in dist or new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    return dist
```
Looks correct. I'll produce this. 
Self-Correction/Verification during thought:
- Does `graph.get(u, [])` handle nodes that are only targets? Yes, returns `[]`.
- Does it handle `start` not in `graph`? Yes, returns `[]`, loop finishes, returns `{"start": 0.0}`. Correct.
- Unreachable nodes omitted? Yes, only added when reached.
- `heapq` used? Yes.
- Standard library only? Yes.
- Signature matches? Yes.
All constraints satisfied.
Ready. 
Output matches the code block.✅
Proceeds. 
[Output Generation] -> *Proceeds*