Data Structures & Algorithms

Dijkstra's Algorithm

Master Dijkstra's algorithm for your coding interviews. Our guide covers the shortest path problem, implementation details with priority queues, and AI-powered practice to solidify your skills.

Dijkstra's Algorithm Implementation

Here is a Python implementation of Dijkstra's algorithm using a priority queue (min-heap) for efficiency.


import heapq

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

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_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(priority_queue, (distance, neighbor))

    return distances

AI Coach Tip: The key to an efficient Dijkstra's implementation is using a priority queue (min-heap). This allows you to always explore the most promising path first. Be prepared to discuss its time complexity: O(E log V) with a priority queue, where V is the number of vertices and E is the number of edges.