How does Dijkstra's algorithm work in Python?

Can you explain how Dijkstra's algorithm works in Python?

Sure! Dijkstra's algorithm finds the shortest path from a starting node to all other nodes in a graph.

What data structures do I need to implement it?

You'll typically use a priority queue to efficiently get the next node with the smallest distance.

Can you show me a simple code example?

Absolutely! Here's a basic implementation:

import heapq

def dijkstra(graph, start):
    queue = [(0, start)]
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

What are the time and space complexities of this algorithm?

The time complexity is O((V + E) log V) and the space complexity is O(V), where V is the number of vertices and E is the number of edges.