Java Dijkstra's Algorithm Tutorial 🎯

Welcome to our deep dive into Dijkstra's Algorithm using Java! In this lesson, we'll explore how to implement this popular graph traversal algorithm to find the shortest paths between nodes in a graph. By the end of this tutorial, you'll be able to solve real-world problems using Dijkstra's Algorithm.

Understanding Dijkstra's Algorithm 📝

Dijkstra's Algorithm is a graph traversal algorithm that finds the shortest paths between nodes (vertices) in a graph. It works for both weighted and unweighted graphs.

Weighted Graph: A graph with weight or cost associated with each edge.
Unweighted Graph: A graph where all edges have the same weight (usually 1).

Why Dijkstra's Algorithm? ✅

It finds the shortest path between two nodes in a graph.
It can handle both weighted and unweighted graphs.
It works with negative-weight edges, which helps in modeling real-world scenarios.
It doesn't get stuck in infinite loops like some other algorithms.

Implementing Dijkstra's Algorithm in Java 💡

Let's get our hands dirty with some code! We'll create a simple example with a weighted graph.

java

import java.util.*;

class Edge {
    int src;
    int nbr;
    int wt;

    public Edge(int src, int nbr, int wt) {
        this.src = src;
        this.nbr = nbr;
        this.wt = wt;
    }
}

public class Main {
    public static void main(String[] args) {
        // Create the graph
        ArrayList<Edge>[] graph = new ArrayList[6];
        for (int i = 0; i < 6; i++)
            graph[i] = new ArrayList<>();

        // Add edges to the graph
        graph[0].add(new Edge(0, 1, 10));
        graph[0].add(new Edge(0, 4, 5));
        graph[1].add(new Edge(1, 0, 10));
        graph[1].add(new Edge(1, 2, 1));
        graph[1].add(new Edge(1, 3, 15));
        graph[1].add(new Edge(1, 4, 2));
        graph[2].add(new Edge(2, 1, 1));
        graph[2].add(new Edge(2, 3, 3));
        graph[2].add(new Edge(2, 5, 20));
        graph[3].add(new Edge(3, 1, 15));
        graph[3].add(new Edge(3, 2, 3));
        graph[3].add(new Edge(3, 4, 6));
        graph[4].add(new Edge(4, 0, 5));
        graph[4].add(new Edge(4, 1, 2));
        graph[4].add(new Edge(4, 3, 6));
        graph[4].add(new Edge(4, 5, 9));
        graph[5].add(new Edge(5, 2, 20));
        graph[5].add(new Edge(5, 4, 9));

        // Initialize the shortest distances array
        int[] dist = new int[6];
        Arrays.fill(dist, Integer.MAX_VALUE);

        // Set the initial distance of the source node to 0
        dist[0] = 0;

        // Implement Dijkstra's Algorithm
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(0);

        while (!pq.isEmpty()) {
            int u = pq.poll();

            for (Edge edge : graph[u]) {
                int v = edge.nbr;
                int weight = edge.wt;

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(v);
                }
            }
        }

        // Print the shortest distances
        for (int i = 0; i < dist.length; i++)
            System.out.println("Shortest distance from source to node " + i + " is: " + dist[i]);
    }
}

In this code, we first create a graph with weighted edges and initialize an array dist to store the shortest distances from the source node to all other nodes. We then implement Dijkstra's Algorithm, updating the shortest distances for each node as we traverse the graph.

Quiz 💡

That's all for today! In the next lesson, we'll dive deeper into using Dijkstra's Algorithm in more complex scenarios, so stay tuned! 🎯