Check out the Blog Section!

Dijkstra's Algorithm: A Step-by-Step Guide

Jacob Jonas

2/20/20243 min read

a group of blue lights
a group of blue lights

Introduction

Dijkstra's Algorithm is a popular graph traversal algorithm that is used to find the shortest path between two nodes in a graph. It is widely used in various fields such as network routing, transportation planning, and computer science. In this tutorial, we will explore the working of Dijkstra's Algorithm with the help of node examples in Java and visual representations created with parentheses to represent nodes and arrows to represent traversals.

What is Dijkstra's Algorithm?

Dijkstra's Algorithm, named after its inventor Edsger Dijkstra, is an algorithm that finds the shortest path between two nodes in a graph with non-negative edge weights. It starts from a source node and iteratively explores the neighboring nodes, updating the shortest path to each node as it progresses. The algorithm terminates when it has visited all the nodes or when it has found the shortest path to the destination node.

Implementation in Java

Let's start by implementing Dijkstra's Algorithm in Java. We will use a simple graph represented by an adjacency matrix. Each node will be represented by a character, and the edge weights will be represented by integers. Here's an example code snippet:


import java.util.*;

public class DijkstraAlgorithm {

    public static void dijkstra(int[][] graph, int source) {
        int n = graph.length;
        int[] distance = new int[n];
        boolean[] visited = new boolean[n];

        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[source] = 0;

        for (int i = 0; i < n - 1; i++) {
            int minDistance = Integer.MAX_VALUE;
            int minIndex = -1;

            for (int j = 0; j < n; j++) {
                if (!visited[j] && distance[j] < minDistance) {
                    minDistance = distance[j];
                    minIndex = j;
                }
            }

            visited[minIndex] = true;

            for (int j = 0; j < n; j++) {
                if (!visited[j] && graph[minIndex][j] != 0 && distance[minIndex] != Integer.MAX_VALUE &&
                        distance[minIndex] + graph[minIndex][j] < distance[j]) {
                    distance[j] = distance[minIndex] + graph[minIndex][j];
                }
            }
        }

        // Print the shortest distances
        for (int i = 0; i < n; i++) {
            System.out.println("Shortest distance from source to node " + (char) (i + 'A') + ": " + distance[i]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 4, 0, 0, 0, 0, 0, 8, 0},
                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };

        dijkstra(graph, 0);
    }
}

In the above code, we have a graph represented by a 2D array called "graph". We initialize the distance array with maximum values and set the distance of the source node to 0. The algorithm then iterates through all the nodes, selecting the one with the minimum distance from the source that hasn't been visited yet. It updates the distances of the neighboring nodes if a shorter path is found. Finally, it prints the shortest distances from the source node to all other nodes.

Visual Representation

To better understand how Dijkstra's Algorithm works, let's represent the graph using parentheses to represent nodes and arrows to represent traversals. Consider the following graph:


(A) --4-- (B) --8-- (H)
 |           |     / |
 8           11   /  7
 |           |  /   |
(D) --7-- (C) --2-- (G)
 |     /     |
 4   /       2
 |  /        |
(E) --9-- (F)

Starting from node A, we will traverse the graph using Dijkstra's Algorithm:

  1. Visit node A. Set the distance to A as 0.
  2. Visit node B. Set the distance to B as 4.
  3. Visit node H. Set the distance to H as 8.
  4. Visit node D. Set the distance to D as 8.
  5. Visit node C. Set the distance to C as 10.
  6. Visit node G. Set the distance to G as 12.
  7. Visit node F. Set the distance to F as 14.
  8. Visit node E. Set the distance to E as 17.

After traversing all the nodes, we have found the shortest distances from the source node A to all other nodes:


Shortest distance from source to node A: 0
Shortest distance from source to node B: 4
Shortest distance from source to node C: 10
Shortest distance from source to node D: 8
Shortest distance from source to node E: 17
Shortest distance from source to node F: 14
Shortest distance from source to node G: 12
Shortest distance from source to node H: 8

Conclusion

Dijkstra's Algorithm is a powerful tool for finding the shortest path between two nodes in a graph. By understanding its implementation in Java and visualizing the graph traversal, software engineers and students can gain a deeper understanding of its inner workings. Whether it's optimizing network routing or solving complex transportation planning problems, Dijkstra's Algorithm is an essential tool in the arsenal of every software engineer.

Remember, practice is key to mastering algorithms. So, don't hesitate to implement Dijkstra's Algorithm in your own projects and explore its applications in different domains. Happy coding!

© 2024 Jacob Jonas