Featured Post

Trie implementation in C

Dijkstra algorithm implementation in Java


  • 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]));

        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;

        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);
        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 + ") ");

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.