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
from typing import Dict, List, Tuple

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    # Initialize distances with start node at 0.0
    distances = {start: 0.0}
    
    # Min-heap: (distance, node)
    heap = [(0.0, start)]
    
    while heap:
        dist, node = heapq.heappop(heap)
        
        # Skip if we've already found a shorter path to this node
        if dist > distances.get(node, float('inf')):
            continue
        
        # Explore neighbors
        if node in graph:
            for neighbor, weight in graph[node]:
                new_dist = dist + weight
                
                # Update if we found a shorter path
                if neighbor not in distances or new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(heap, (new_dist, neighbor))
    
    return distances
```

The task is to implement Dijkstra's algorithm using `heapq` to find shortest paths from a start node to all reachable nodes in a directed weighted graph.

Key requirements:
1. Use `heapq` for the priority queue
2. Return only reachable nodes (omit unreachable ones)
3. Start node maps to 0.0
4. Weights are non-negative
5. Nodes can appear as targets without being keys in the graph dict
6. Standard library only

Algorithm:
1. Initialize distances with infinity for all nodes, 0 for start
2. Use a min-heap to store (distance, node) pairs
3. Track visited nodes to avoid reprocessing
4. For each node popped from heap, explore its neighbors
5. If a shorter path is found, update distance and push to heap
6. Return only nodes that were reached (distance < infinity)

Let me code this:

```python
import heapq
from typing import Dict, List, Tuple

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    # Initialize distances
    distances = {start: 0.0}
    
    # Min-heap: (distance, node)
    heap = [(0.0, start)]
    
    # Track visited nodes to avoid reprocessing
    visited = set()
    
    while heap:
        dist, node = heapq.heappop(heap)
        
        # Skip if already processed with shorter distance
        if node in visited:
            continue
        
        visited.add(node)
        
        # Explore neighbors
        if node in graph:
            for neighbor, weight in graph[node]:
                new_dist = dist + weight
                
                # Only update if we found a shorter path and haven't visited yet
                if neighbor not in visited and (neighbor not in distances or new_dist < distances[neighbor]):
                    distances[neighbor] = new_dist
                    heapq.heappush(heap, (new_dist, neighbor))
    
    return distances
```

Wait, I need to reconsider the visited logic. In Dijkstra's algorithm, once a node is popped from the heap with its shortest distance, we don't need to process it again. However, I should be careful about the condition for updating distances.

Actually, the standard approach is:
1. Pop the node with smallest distance
2. If this distance is greater than what we already know for this node, skip it (lazy deletion)
3. Otherwise, process neighbors

Let me refine:

```python
import heapq

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    # Initialize distances with start node at 0
    distances = {start: 0.0}
    
    # Min-heap: (distance, node)
    heap = [(0.0, start)]
    
    while heap:
        dist, node = heapq.heappop(heap)
        
        # Skip if we've already found a shorter path to this node
        if dist > distances.get(node, float('inf')):
            continue
        
        # Explore neighbors
        if node in graph:
            for neighbor, weight in graph[node]:
                new_dist = dist + weight
                
                # Update if we found a shorter path
                if neighbor not in distances or new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(heap, (new_dist, neighbor))
    
    return distances
```

This approach uses lazy deletion - when we pop a node with a distance greater than what we've already recorded, we skip it. This is more efficient than maintaining a separate visited set.

I should verify the logic handles the test cases correctly. For the first example with nodes a, b, c, d, the algorithm should find the shortest paths: a→b (1.0), a→c via b (3.0), and a→d via c (4.0). For the second example with the island, it should only return reachable nodes from a, excluding island since it's not reachable.

The implementation looks solid. I'll use the standard library only with heapq, and ensure the function signature matches the requirements exactly.