Understanding Dijkstra’s Algorithm: A Guide to Shortest Path Finding

· 6 min read

Hey everyone, it’s alanturrr1703 back again! 😄 Today, we’re diving into one of the most well-known algorithms in computer science: Dijkstra’s Algorithm. This algorithm is widely used to find the shortest path from a starting node to all other nodes in a weighted graph, making it indispensable in areas like network routing and GPS navigation.

In this blog, we’ll cover the fundamentals of Dijkstra’s algorithm, walk through an example, and provide detailed pseudocode to help you implement it efficiently.

Let’s dive right into it! 🚀

What is Dijkstra’s Algorithm?

Dijkstra’s Algorithm is a greedy algorithm used to find the shortest path between nodes in a weighted graph. It calculates the shortest path from a starting node (source) to all other nodes in the graph. It works only on graphs with non-negative weights.

Key Concepts:

  • Shortest Path: The path between two nodes with the smallest sum of edge weights.
  • Weighted Graph: A graph where edges have weights, representing the cost of moving from one node to another.

Problem Statement:

Given a graph and a starting node, find the shortest path to all other nodes. The graph can be represented using an adjacency list or adjacency matrix.

How Dijkstra’s Algorithm Works

Basic Steps:

  1. Initialize: Create a distance array to store the shortest distance from the source to each node. Set the distance to the source as 0 and to all other nodes as infinity.
  2. Select the Node: Pick the unvisited node with the smallest distance (initially the source node).
  3. Update Distances: For each neighboring node, calculate the tentative distance from the source. If this new distance is shorter than the currently known distance, update the distance.
  4. Mark the Node as Visited: Once all neighboring nodes are considered, mark the current node as visited, meaning we have found the shortest path to this node.
  5. Repeat: Continue selecting the next unvisited node with the smallest distance and repeat the process until all nodes are visited.

Pseudocode for Dijkstra’s Algorithm

Data Structures:

  • Graph: Adjacency list or matrix representation of the graph.
  • Distance Array (dist[]): Stores the shortest distance from the source node to each node.
  • Priority Queue (Min-Heap): To efficiently select the node with the smallest distance.
  • Visited Array (visited[]): Keeps track of whether a node has been visited.
Function Dijkstra(graph, source):
    # Number of nodes in the graph
    n = length(graph)

    # Distance array initialized to infinity
    dist = array of size n, initialized to infinity
    dist[source] = 0

    # Visited array to keep track of visited nodes
    visited = array of size n, initialized to False

    # Priority queue (min-heap) to select the node with the smallest distance
    pq = PriorityQueue()
    pq.push((0, source))  # (distance, node)

    # Main loop of the algorithm
    While not pq.isEmpty():
        # Extract node with smallest distance
        currentDist, u = pq.pop()

        # Skip if the node is already visited
        If visited[u]:
            Continue

        # Mark the current node as visited
        visited[u] = True

        # Iterate through all neighbors of the current node
        For each neighbor, weight in graph[u]:
            v = neighbor
            newDist = currentDist + weight

            # If a shorter path is found, update the distance and push to pq
            If newDist < dist[v]:
                dist[v] = newDist
                pq.push((newDist, v))

    Return dist  # Returns the shortest distance to all nodes from the source

Explanation of the Pseudocode:

  1. Initialize: The dist[] array is initialized to infinity for all nodes except the source node, which is set to 0. The visited[] array helps ensure we don’t revisit nodes.
  2. Priority Queue: The priority queue stores pairs (distance, node) to efficiently extract the node with the smallest distance.
  3. Main Loop: The algorithm selects the unvisited node with the smallest distance (using the priority queue), marks it as visited, and updates distances for its neighbors.
  4. Distance Update: For each neighbor of the current node, if a shorter path is found, the distance is updated, and the neighbor is pushed onto the priority queue.
  5. Repeat: The process continues until all nodes are visited, and the dist[] array contains the shortest distances from the source to all other nodes.

Example Walkthrough

Let’s go through a small example to understand how Dijkstra’s Algorithm works step-by-step.

Graph Representation:

        2
    (A)-----(B)
    / |     / |
   4  |    1  | 3
  /   |   /   |
(C)   |  7    (D)
  \   |       /
   1  |      5
    \ |     /
    (E)-----
  • Nodes: A, B, C, D, E
  • Edges (weights):
    • A -> B (2)
    • A -> C (4)
    • A -> E (1)
    • B -> D (3)
    • B -> E (1)
    • C -> E (1)
    • E -> D (5)

Starting Node: A

Step 1: Initialize

  • dist = [0, ∞, ∞, ∞, ∞] (Distances to A, B, C, D, E)
  • Priority Queue: [(0, A)]

Step 2: Process Node A

  • Current node: A, Current distance: 0
  • Neighbors: B(2), C(4), E(1)
  • Update distances:
    • dist[B] = 2
    • dist[C] = 4
    • dist[E] = 1
  • Priority Queue: [(1, E), (2, B), (4, C)]

Step 3: Process Node E

  • Current node: E, Current distance: 1
  • Neighbors: A, B(1), C(1), D(5)
  • Update distances:
    • dist[B] = min(2, 1 + 1) = 2
    • dist[C] = min(4, 1 + 1) = 2
    • dist[D] = 1 + 5 = 6
  • Priority Queue: [(2, B), (2, C), (6, D)]

Step 4: Process Node B

  • Current node: B, Current distance: 2
  • Neighbors: A, D(3), E(1)
  • Update distances:
    • dist[D] = min(6, 2 + 3) = 5
  • Priority Queue: [(2, C), (5, D), (6, D)]

Step 5: Process Node C

  • Current node: C, Current distance: 2
  • Neighbors: A, E(1)
  • No updates needed.
  • Priority Queue: [(5, D), (6, D)]

Step 6: Process Node D

  • Current node: D, Current distance: 5
  • Neighbors: B, E
  • No updates needed.
  • Priority Queue: [(6, D)]

Step 7: Process Node D (again)

  • Current node: D, Current distance: 6 (already processed)

Final Distances:

  • dist = [0, 2, 2, 5, 1]
  • Shortest distances from A:
    • To B: 2
    • To C: 2
    • To D: 5
    • To E: 1

Time Complexity of Dijkstra’s Algorithm

The time complexity of Dijkstra’s Algorithm depends on how the graph is represented and the data structure used for the priority queue.

  • Priority Queue (Min-Heap): If we use a priority queue implemented as a min-heap, the complexity is:
    • O(E log V), where E is the number of edges, and V is the number of vertices.

This is efficient for sparse graphs where the number of edges is much less than the number of vertices squared.

When to Use Dijkstra’s Algorithm

Dijkstra’s Algorithm is ideal for:

  • Finding shortest paths in weighted graphs with non-negative weights.
  • Routing in network systems, such as finding the shortest path in computer networks or GPS-based navigation systems.
  • Planning and scheduling: Used to optimize routes or tasks in logistics and project management.

However, Dijkstra’s algorithm cannot handle graphs with negative weights. For those cases, you would use Bellman-Ford’s Algorithm.

Wrapping It Up

In this blog, we explored Dijkstra’s Algorithm, one

of the most important algorithms for finding the shortest path in a weighted graph. We covered the key steps, provided pseudocode, and walked through a sample graph to understand how it works. Dijkstra’s algorithm is efficient, but it requires non-negative edge weights.

Understanding Dijkstra’s algorithm will help you tackle many graph-based problems, from network routing to optimization tasks.

That’s all for today! I hope this post gave you a clear understanding of Dijkstra’s Algorithm. Until next time, happy coding! 🚀