Dijkstra's Algorithm

Dijkstra's algorithm is a graph search algorithm that finds the shortest paths from a single source node to all other nodes in a weighted graph with non-negative edge weights. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

Algorithm Workflow

Dijkstra's algorithm operates under the assumption that all edge weights in the graph are non-negative. This allows the algorithm to use a greedy strategy, prioritizing the lowest weight edges first, which guarantees finding the shortest path from the source node to every other node in the graph.

1. Initialization: Start with the source vertex, set its distance to zero, and all other vertices' distances to infinity.
2. Priority Queue: Maintain a priority queue (min-heap) to fetch the next vertex with the smallest distance efficiently.
3. Relaxation: For each extracted vertex, update the distances to its adjacent vertices.
4. Update Distances: If the distance to a vertex via the current vertex is shorter than the known distance, update it.
5. Repeat: Continue until the priority queue is empty or all reachable vertices have been processed.

Complexity

• Algorithm Type: Greedy algorithm.
• Purpose: Finds the shortest path from a source node to all other nodes in a weighted graph with non-negative weights.
• Complexity: The time complexity can vary:
  • $O((V + E) \log V)$ using a priority queue.
  • $O(V^2)$ using an array, suitable for dense graphs.

Pseudocode

function Dijkstra(Graph, source):
    create vertex set Q

    for each vertex v in Graph:             
        dist[v] ← INFINITY                 
        prev[v] ← UNDEFINED                
        add v to Q                      
    dist[source] ← 0                        
    
    while Q is not empty:
        u ← vertex in Q with min dist[u]   
        remove u from Q

        for each neighbor v of u:           
            alt ← dist[u] + length(u, v)
            if alt < dist[v]:               
                dist[v] ← alt
                prev[v] ← u

    return dist[], prev[]

Limitations

Dijkstra's algorithm does not work with graphs that have negative weight edges. For such graphs, algorithms like the Bellman-Ford or the Floyd-Warshall algorithm are used.

Implementation in Python

Below is a Python implementation using heapq for the priority queue, which is a common practice for efficiency.

import heapq

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

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        # Nodes can get added to the priority queue multiple times. We only
        # process a vertex the first time we remove it from the priority queue.
        if current_distance > distances[current_vertex]:
            continue

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

            # Only consider this new path if it's better
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

Example Usage

Here's how you might use the function on a simple graph:

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
start_vertex = 'A'
shortest_paths = dijkstra(graph, start_vertex)
print(shortest_paths)  # Output will show the shortest paths from 'A' to all other nodes