Dijkstra's Algorithm in Data Structure

Dijkstra's Algorithm finds the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights.

How It Works

• Initialize the distance to the source as 0 and all others as infinity.
• Use a priority queue to repeatedly select the unvisited vertex with the smallest known distance.
• Relax all edges from that vertex — update neighbor distances if a shorter path is found.
• Mark the vertex as visited and repeat until all vertices are processed.

import heapq

def dijkstra(graph, source):
    distances = {node: float('inf') for node in graph}
    distances[source] = 0
    pq = [(0, source)]

    while pq:
        current_dist, node = heapq.heappop(pq)
        if current_dist > distances[node]:
            continue
        for neighbor, weight in graph[node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

Complexity

Limitations

Dijkstra's Algorithm does not work correctly with negative edge weights; the Bellman-Ford algorithm should be used instead in that case.

Applications

• GPS navigation and route planning.
• Network routing protocols (e.g., OSPF).
• Flight/travel booking systems to find the cheapest or fastest route.