Dijkstra

Dijkstra is an algorithm for finding the shortest path from a single source to all vertices in a weighted graph. It uses a greedy approach with a priority queue.

Requirements

• The graph must be weighted.
• There must be no negative edges.

Concept

Graph:
    A --4--> B
    |         |
    2         3
    |         |
    v         v
    C --5--> D

Shortest from A:
A: 0, B: 4, C: 2, D: 7 (A->C->D = 2+5=7)

Algorithm

1. Set the distance of every vertex = infinity, source = 0.
2. Insert the source into the priority queue.
3. Take the vertex with the smallest distance.
4. Update the distance to all neighbors if it is smaller.
5. Repeat until the priority queue is empty.

Implementation

import heapq

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

    while pq:
        dist, u = heapq.heappop(pq)

        if dist > distances[u]:
            continue

        for v, weight in graph[u]:
            if dist + weight < distances[v]:
                distances[v] = dist + weight
                previous[v] = u
                heapq.heappush(pq, (distances[v], v))

    return distances, previous

# Reconstruct path
def get_path(previous, target):
    path = []
    current = target
    while current:
        path.append(current)
        current = previous[current]
    return path[::-1]

Example

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8)],
    'D': [('B', 5), ('C', 8)]
}

distances, previous = dijkstra(graph, 'A')
print(distances)  # {'A': 0, 'B': 3, 'C': 2, 'D': 8}

print(get_path(previous, 'D'))  # ['A', 'C', 'B', 'D']

Time Complexity

V = vertices, E = edges

Important Notes

• No negative edges: It can produce wrong results.
• Greedy: Always processes the closest vertex first.
• Relaxation: Updates the distance when a shorter path is found.

Applications

• GPS and navigation (Google Maps).
• Network routing (OSPF).
• Shortest path in games.
• Social network analysis.

Dijkstra solves single-source shortest paths. An MST connects all vertices at minimum cost.