py-11-dijkstra

1.000

8/8 tests· algorithms

Proposed solution

```python
import heapq
from collections import defaultdict

def dijkstra(graph: dict[str, list[tuple[str, float]]], start: str) -> dict[str, float]:
    # Initialize distances with infinity for all nodes
    distances = defaultdict(lambda: float('inf'))
    distances[start] = 0.0
    
    # Priority queue: (distance, node)
    pq = [(0.0, start)]
    visited = set()
    
    while pq:
        current_dist, current_node = heapq.heappop(pq)
        
        # Skip if already visited
        if current_node in visited:
            continue
            
        visited.add(current_node)
        
        # Update distances to neighbors
        for neighbor, weight in graph.get(current_node, []):
            if neighbor not in visited:
                new_dist = current_dist + weight
                if new_dist < distances[neighbor]:
                    distances[neighbor] = new_dist
                    heapq.heappush(pq, (new_dist, neighbor))
    
    # Convert defaultdict to regular dict and remove unreachable nodes
    result = {}
    for node, dist in distances.items():
        if dist != float('inf'):
            result[node] = dist
    
    return result
```

Test output (stdout)

........                                                                 [100%]
8 passed in 0.01s

System prompt

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.