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.

To solve this problem, we need to compute the shortest-path distance from a given start node to every reachable node in a weighted directed graph using Dijkstra's algorithm. The graph is represented as a dictionary where each key is a node, and the value is a list of tuples representing edges to other nodes with their respective weights.

### Approach
1. **Initialization**: Start by initializing a dictionary to keep track of the shortest distances from the start node to all other nodes. The start node's distance is set to 0, and all other nodes are initialized to infinity.
2. **Priority Queue**: Use a priority queue (min-heap) to process nodes in order of their current shortest distance. This helps in efficiently fetching the next node with the smallest tentative distance.
3. **Processing Nodes**: For each node popped from the heap, check if a shorter path to the node has already been found. If so, skip processing this node. Otherwise, update the shortest distances to all reachable neighbors and push these neighbors into the heap for further processing.
4. **Dynamic Node Handling**: Nodes that are not present in the graph but appear as targets in edges are handled dynamically. They are added to the distances dictionary with an initial distance of infinity and processed if a shorter path is found.

### Solution Code
```python
import heapq

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    distances = {start: 0.0}
    heap = []
    heapq.heappush(heap, (0.0, start))
    
    while heap:
        current_dist, u = heapq.heappop(heap)
        
        if current_dist > distances[u]:
            continue
        
        for v, weight in graph.get(u, []):
            if v not in distances:
                distances[v] = float('inf')
            
            new_dist = current_dist + weight
            if new_dist < distances[v]:
                distances[v] = new_dist
                heapq.heappush(heap, (new_dist, v))
    
    return distances
```

### Explanation
- **Initialization**: The distances dictionary is initialized with the start node having a distance of 0.0. The priority queue is initialized with the start node and its distance.
- **Heap Processing**: The heap is processed in a loop. For each node, if a shorter path is found, the node's neighbors are updated with the new shortest distance and pushed into the heap.
- **Dynamic Handling**: Nodes that are not initially in the graph but appear as targets in edges are dynamically added to the distances dictionary with an initial distance of infinity. If a shorter path is found, their distance is updated and they are processed further.

This approach ensures that all reachable nodes are processed efficiently, and the shortest paths are computed correctly using Dijkstra's algorithm with a priority queue.

Okay, I need to implement the Dijkstra algorithm using heapq in Python. The function is supposed to take a graph and a start node, and return the shortest distance from the start to every reachable node. Let's think about how to approach this.

First, let's understand the problem. The graph is a dictionary where each key is a node, and the value is a list of tuples representing edges. Each tuple has a destination node and a weight. The weights are non-negative, which is good because Dijkstra's algorithm works with non-negative weights.

The function needs to return a dictionary where each key is a reachable node from the start, and the value is the shortest distance. If a node is unreachable, it's omitted.

So, the steps I need to follow are:

1. Initialize the distances. All nodes start with infinity except the start node, which is 0.
2. Use a priority queue (min-heap) to process nodes in order of their current shortest distance. The heap will store tuples of (distance, node).
3. For each node popped from the heap, check if we've already found a shorter path. If so, skip processing this node.
4. Otherwise, for each neighbor of the current node, calculate the tentative distance. If this is less than the current known distance, update it and add the neighbor to the heap.
5. Continue until the heap is empty.

Wait, but how do I handle nodes that are not in the graph? For example, if a node is only a target in some edges but not a key in the graph, it's still a valid node. So, I need to make sure that all nodes are considered, even if they don't appear as keys in the graph.

Hmm, so the initial distances should include all nodes that are reachable. But how do I know all the nodes in the graph? Because the graph is a dictionary, the keys are the nodes that have outgoing edges. But other nodes might exist as targets in the edges. So, perhaps I should collect all possible nodes first.

Wait, but that's not efficient. Maybe it's better to process nodes as we encounter them. So, when we process a node, we look at its neighbors. If a neighbor hasn't been added to the distances yet, we initialize it with infinity and add it to the heap if needed.

So, the plan is:

- Create a dictionary to keep track of the shortest distances. Initialize it with the start node as 0, and all others as infinity. But wait, how do I know all the nodes? Because the graph may have nodes that are only targets. So perhaps, I should collect all nodes from the graph's keys and all the edges' targets.

Alternatively, I can collect all nodes by iterating through all the edges and adding their targets to a set. Then, the initial distances will be for all these nodes, set to infinity, except the start.

But that might be a bit involved. Alternatively, during the processing, if a node is encountered that's not in the distances, we can add it with infinity.

Wait, but in the initial step, the start node is added to the heap with distance 0. Then, for each neighbor, if it's not in the distances, we add it with a tentative distance.

So, perhaps the initial distances can be a dictionary that starts with the start node as 0, and all others are added as they are encountered.

Wait, but for nodes that are not reachable, we shouldn't include them in the result. So, the initial distances should include all nodes that are reachable, but how do I know which ones are reachable without traversing the graph?

Hmm, perhaps the initial distances can be built as follows:

- Initialize the distances dictionary with the start node as 0.
- For all other nodes, they are added to the distances as we process them.

Wait, but that might not capture all nodes. For example, if a node is only a target in some edge, but not a key in the graph, it's a valid node. So, when processing a node, we look at its edges, and for each destination, if it's not in the distances, we add it with infinity.

So, the initial step is:

- distances = {start: 0}
- heap = [(0, start)]
- visited = set()

Wait, but in Dijkstra's algorithm, we don't necessarily need a visited set because once a node is popped from the heap, we've found the shortest path to it. So, we can skip processing it again if it's already been processed.

So, the algorithm steps:

1. Initialize the distances dictionary with the start node as 0, and all other nodes as infinity. But since we don't know all nodes upfront, perhaps we can handle it dynamically.

Wait, perhaps the initial distances can be a defaultdict with a default value of infinity. But in Python, using a regular dictionary and checking for existence might be more efficient.

Alternatively, during the processing, when we encounter a node that's not in the distances, we add it with infinity.

So, let's outline the code structure.

First, import heapq.

Then, in the function:

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

Initialize the distances:

distances = {start: 0.0}

priority queue: heap, which starts with (0.0, start)

heapq.heapify(heap) or push the start.

Wait, no, we can push the start node into the heap.

Then, while the heap is not empty:

    current_distance, u = heappop(heap)

    if u is not in distances: continue (since it's already been processed with a shorter distance)

    for each (v, weight) in graph.get(u, []):

        if v not in distances:
            distances[v] = float('inf')

        new_distance = current_distance + weight

        if new_distance < distances[v]:
            distances[v] = new_distance
            heappush(heap, (new_distance, v))

Wait, but this might not capture all nodes. For example, if a node is a target in some edge but not a key in the graph, it's a valid node. So, when processing u, we look at all its edges, and for each v, if it's not in distances, we add it with infinity.

But wait, in the initial step, the distances only have the start node. So, when processing the start node, we look at all its edges, and for each v, add them to distances with infinity, then push them into the heap.

But what about nodes that are not in the graph? For example, if a node is only a target in some ed
…[8452 chars elided]…
("b", 1)], "b": [("c", 2)], "c": []}, start is 'a'. The result is {'a':0, 'b':1, 'c':3}.

Yes.

Now, what about when the graph is empty except for the start node? Like, graph = {}, start is 'a'. Then, the result is {'a':0}.

Yes.

Another edge case: graph = {"a": [("a", 0)]}, start is 'a'. The distance to 'a' is 0, but the edge creates a loop. So, when processing 'a', the new distance is 0, which is not better than the current 0, so nothing changes. So, the result is {'a':0}.

Yes.

Another case: graph = {"a": [("b", 5)], "b": [("a", 3)]}, start is 'a'. The distance to 'b' is 5, but 'b' has an edge back to 'a' with weight 3. So, when 'a' is processed, 'b' is added with 5. Then, when 'b' is processed, it adds a new distance to 'a' as 5+3=8, which is worse than 0, so nothing changes. So, the result is {'a':0, 'b':5}.

Yes.

So, the code seems to handle all these cases.

Now, let's think about the data structures again.

The distances dictionary is built dynamically. For each node processed, its edges are considered, and the distances are updated as needed.

The heap can have multiple entries for the same node, but the algorithm correctly skips processing a node if a shorter distance has already been recorded.

Now, the function returns the distances dictionary, which includes all reachable nodes. Unreachable nodes are not present in the dictionary.

Wait, but in the code, the initial distances is {start:0}, and for each node processed, their neighbors are added to distances if not present. So, any node that is reachable will be in the distances dictionary. Nodes that are not reachable are not added, so they are omitted from the result.

Yes.

So, the code should work as intended.

Now, let's write the code.

But wait, in the code, the initial heap is pushed with (0.0, start). Then, in the loop, we pop (current_dist, u). Then, for each (v, weight) in graph.get(u, []), we check if v is in distances. If not, add it with infinity. Then, calculate new_dist and update if better.

Yes.

So, the code should be as follows.