Introduction

Dijkstra's algorithm is a classic algorithm in graph theory used for finding the shortest paths from a single source vertex to all other vertices in a weighted graph, where the weights are non-negative. It is a greedy algorithm, meaning it makes the locally optimal choice at each step with the hope of finding the global optimum. The algorithm was conceived by computer scientist Edsger W. Dijkstra in 1956 and published in 1959.

This document provides a comprehensive explanation of Dijkstra's algorithm, covering its principles, pseudocode, example execution, complexity analysis with different data structures, and limitations.

Detailed Explanation of Dijkstra's Algorithm

Core Idea

Dijkstra's algorithm works by iteratively exploring the vertices of the graph. It maintains a set of visited vertices for which the shortest path from the source is already known, and a set of unvisited vertices. At each step, it selects the unvisited vertex with the smallest distance from the source (the "current" vertex), marks it as visited, and updates the distances to its neighbors. This process continues until all vertices have been visited or until the destination vertex (if a specific target is desired) has been reached.

Key Concepts

• Graph: A collection of vertices (nodes) and edges connecting those vertices.
• Weighted Graph: A graph where each edge has a numerical weight associated with it, representing the cost of traversing that edge.
• Single-Source Shortest Paths: Finding the shortest path from a specified source vertex to all other vertices in the graph.
• Non-Negative Edge Weights: Dijkstra's algorithm requires that all edge weights are non-negative (zero or positive). It does not work correctly with negative edge weights.
• Distance: The cost (sum of edge weights) of the path from the source vertex to a given vertex.
• Visited Set: The set of vertices for which the shortest path from the source has already been determined.
• Priority Queue (Optional): A data structure used to efficiently find the unvisited vertex with the smallest distance.

Pseudocode

  function Dijkstra(graph, source):
    // Initialize distances:
    dist = a dictionary mapping each vertex to infinity, except for the source vertex
    dist[source] = 0

    // Initialize visited set:
    visited = an empty set

    // Initialize priority queue (optional):
    priorityQueue = a priority queue containing all vertices, prioritized by their distance (dist) from the source

    while there are unvisited vertices (either visited.size() < graph.numVertices or priorityQueue is not empty):
        // Find the unvisited vertex with the smallest distance from the source:

        if priorityQueue is used:
            u = priorityQueue.extractMin()  //Get and remove the vertex with the smallest dist
        else:
            u = vertex with minimum dist[u] among all unvisited vertices. If no unvisited vertex is left, break.

        if u is null: // All remaining unvisited vertices are unreachable
            break;

        visited.add(u)

        // For each neighbor v of u:
        for each neighbor v of u:
            //Calculate the alternative distance to v through u
            alt = dist[u] + weight(u, v)

            //If this alternative distance is shorter than the current distance to v:
            if alt < dist[v]:
                dist[v] = alt
                // Optionally, update v's priority in the priority queue
                if priorityQueue is used:
                    priorityQueue.decreaseKey(v, alt)  //Update the priority of v in the priority queue
    return dist // Returns a dictionary of shortest distances from the source to each vertex.  

Example Execution

Consider the following weighted graph:

(Assume a graph_example.png is available showing a small graph. Example: Vertices A, B, C, D. Edges: A-B(4), A-C(2), B-C(1), B-D(5), C-D(8))

Let's run Dijkstra's algorithm with 'A' as the source vertex.

1. Initialization:
   • dist[A] = 0
   • dist[B] = Infinity
   • dist[C] = Infinity
   • dist[D] = Infinity
   • visited = {}
2. Iteration 1:
   • Current vertex: A (smallest distance)
   • visited = {A}
   • Neighbors of A: B (weight 4), C (weight 2)
   • Update dist[B] to 4 (0 + 4)
   • Update dist[C] to 2 (0 + 2)
3. Iteration 2:
   • Current vertex: C (smallest distance among unvisited vertices: B, C, D)
   • visited = {A, C}
   • Neighbors of C: B (weight 1), D (weight 8)
   • Update dist[B] to 3 (2 + 1) (shorter than the previous 4)
   • Update dist[D] to 10 (2 + 8)
4. Iteration 3:
   • Current vertex: B (smallest distance among unvisited vertices: B, D)
   • visited = {A, C, B}
   • Neighbors of B: D (weight 5)
   • Update dist[D] to 8 (3 + 5) (shorter than the previous 10)
5. Iteration 4:
   • Current vertex: D (smallest distance among unvisited vertices: D)
   • visited = {A, C, B, D}
   • Neighbors of D: None
6. Final Distances:
   • dist[A] = 0
   • dist[B] = 3
   • dist[C] = 2
   • dist[D] = 8

Complexity Analysis

The time complexity of Dijkstra's algorithm depends on the data structure used to implement the priority queue (or its equivalent when a priority queue is not explicitly used).

• Without Priority Queue (Linear Search): In this simple implementation, finding the vertex with the smallest distance in each iteration takes O(V) time, where V is the number of vertices. The outer loop runs V times, and the inner loop (iterating through neighbors) takes O(E) time in total. Therefore, the overall time complexity is O(V² + E), which simplifies to O(V²) for dense graphs where E is close to V².
• Priority Queue (Binary Heap): Using a binary heap as a priority queue provides O(log V) time complexity for both extractMin (removing the vertex with the smallest distance) and decreaseKey (updating a vertex's distance in the priority queue) operations. The extractMin operation is performed V times, and the decreaseKey operation is performed at most E times (once for each edge). Therefore, the overall time complexity is O(V log V + E log V), which can be written as O((V + E) log V). For connected graphs, E >= V-1, so this simplifies to O(E log V).
• Priority Queue (Fibonacci Heap): A Fibonacci heap provides O(1) amortized time complexity for decreaseKey and O(log V) for extractMin. Therefore, the overall time complexity becomes O(V log V + E), which is the most efficient for sparse graphs (where E is much smaller than V²). However, Fibonacci heaps are generally more complex to implement.

Space Complexity: The space complexity is primarily determined by the distance array (dist) and the visited set, both of which require O(V) space. The priority queue (if used) also contributes O(V) space. Therefore, the overall space complexity is O(V).

Limitations

Dijkstra's algorithm has the following limitations:

• Non-Negative Edge Weights: It does not work correctly with negative edge weights. If the graph contains negative cycles (a cycle where the sum of the edge weights is negative), Dijkstra's algorithm may produce incorrect results or even loop indefinitely. For graphs with negative edge weights, the Bellman-Ford algorithm or the Floyd-Warshall algorithm should be used.
• Single Source: It computes the shortest paths from a single source vertex. To find shortest paths between all pairs of vertices, algorithms like Floyd-Warshall are more suitable.
• Directed vs. Undirected Graphs: Dijkstra's algorithm can be applied to both directed and undirected graphs.