Dijkstra algorithm implementation in Java

Purpose

• Finds the shortest paths from a single source vertex to all other vertices in a weighted graph.
• Commonly used in GPS navigation, network routing, and logistics planning.

Key Concepts

• Weighted Graph: A set of vertices (nodes) connected by edges with associated weights (distances, costs, etc.).
• Source Vertex: The starting point for finding shortest paths.
• Shortest Path: The path with the minimum total weight between two vertices.

Algorithm Steps

1. Initialization:

   • Create a set S to store visited vertices (initially empty).
   • Initialize an array distances with infinite values for all vertices except the source, which is set to 0.
   • Create a priority queue Q to store vertices, prioritized by their tentative distances.
   • Add the source vertex to Q.

2. Exploration Loop:

   • While Q is not empty:
     • Extract the vertex u with the minimum distance from Q.
     • Add u to the set S (mark as visited).
     • For each neighbor vertex v of u:
       • If v is not visited and the distance to v through u is shorter than its current distance:
         • Update the distance to v in the distances array.
         • Add v to the priority queue Q (or update its priority if already present).

3. Result:

   • The distances array now contains the shortest distances from the source vertex to all other vertices.
   • To reconstruct the actual shortest paths, keep track of the predecessor of each vertex during the exploration.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.Collectors;

public class Dijkstra {

    public static List dijkstra(Graph graph, int source) {
        int[] distances = new int[graph.numVertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[source] = 0;
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(i -> distances[i]));
        pq.offer(source);

        boolean[] visited = new boolean[graph.numVertices];
        while (!pq.isEmpty()) {
            int u = pq.poll();
            visited[u] = true;
            for (Edge edge : graph.adjacencyList.get(u)) {
                int v = edge.to;
                int weight = edge.weight;
                if (!visited[v] && distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                    pq.offer(v);
                }
            }
        }

        return Arrays.stream(distances).boxed().collect(Collectors.toList());
    }

    public static Graph createRandomGraph(int numVertices) {
        Graph graph = new Graph(numVertices);
        Random random = new Random();
        // Add edges with random weights
        for (int i = 0; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                // Decide whether to create an edge with 50% probability
                if (random.nextBoolean()) {
                    int weight = random.nextInt(10) + 1; // Random weight between 1 and 10
                    graph.addEdge(i, j, weight);
                    graph.addEdge(j, i, weight); // Add reverse edge for undirected graph (if needed)
                }
            }
        }
        return graph;
    }

    public static void main(String[] args) {
        // Create a sample graph
        Graph graph = createRandomGraph(9);
        graph.visualize();
        int source = 0;
        List distances = dijkstra(graph, source);
        System.out.println("Shortest distances from " + source + ": " + distances);
    }

    public static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static class Graph {
        int numVertices;
        List> adjacencyList;

        Graph(int numVertices) {
            this.numVertices = numVertices;
            adjacencyList = new ArrayList<>();
            for (int i = 0; i < numVertices; i++) {
                adjacencyList.add(new ArrayList<>());
            }
        }

        void addEdge(int from, int to, int weight) {
            adjacencyList.get(from).add(new Edge(to, weight));
        }

        void visualize() {
            System.out.println("Graph Visualization:\n");
            for (int vertex = 0; vertex < numVertices; vertex++) {
                System.out.print(vertex + " -> ");
                for (Edge edge : adjacencyList.get(vertex)) {
                    System.out.print(edge.to + "(" + edge.weight + ") ");
                }
                System.out.println();
            }
        }
    }
}

Explanation of code

• Graph Representation

  • The Graph class models a graph using an adjacency list, where each vertex stores a list of its connected edges and their weights.
  • The Edge class encapsulates the destination vertex and weight of an edge.

• Dijkstra's Algorithm Implementation

  • The dijkstra(Graph, source) method implements the algorithm's logic:
    • It maintains a priority queue to explore vertices in order of their tentative distances.
    • It iteratively relaxes edges to update distances and explore reachable vertices.
    • It ultimately returns a list of the shortest distances from the source vertex to all other vertices.

• Random Graph Generation

  • The createRandomGraph(numVertices) method generates a graph with a specified number of vertices and randomly assigns edges with weights between 1 and 10.