Home Data Structures and Algorithms with Java Dijkstra’s Algorithm in Java

Lesson 42 of 48

In Progress

← Previous Next→

Dijkstra’s Algorithm in Java

Yasin Cakal

Dijkstra’s Algorithm is a powerful algorithm used in graph theory to find the shortest path between two vertices. It was developed by Edsger Dijkstra, a Dutch computer scientist, in 1956 and is now one of the most widely used algorithms in computer science. It is used in many applications and is often used to find the shortest path between two locations on a map. Dijkstra’s Algorithm is highly efficient and has a time complexity of O(V^2 + E), where V is the number of vertices and E is the number of edges in the graph. In this article, we will discuss how Dijkstra’s Algorithm works, its time and space complexity, and how to implement it in Java.

How Dijkstra’s Algorithm Works

Dijkstra’s Algorithm is a greedy algorithm that works by starting at one vertex and exploring all possible paths from it to other vertices. As it explores each path, it keeps track of the cost of each path and the total cost of the path so far. Once all the paths have been explored, it will have found the shortest path from the starting vertex to every other vertex.

The algorithm works by using a priority queue. This queue is used to store all the paths that have been explored and the total cost of each path. The priority queue is sorted based on the cost of each path, so the path with the lowest cost is always at the top of the queue. Then, the algorithm takes the path at the top of the queue and explores all possible paths from that vertex. After exploring all the paths, the algorithm updates the total cost of each path and puts them back in the priority queue. This process is repeated until the queue is empty.

Time Complexity

The time complexity of Dijkstra’s Algorithm is O(V^2 + E), where V is the number of vertices in the graph and E is the number of edges. This means that the algorithm can be used to solve large graphs in a reasonable amount of time.

Space Complexity

The space complexity of Dijkstra’s Algorithm is O(V), where V is the number of vertices in the graph. This means that the algorithm requires a relatively small amount of memory to run.

Implementing Dijkstra’s Algorithm in Java

Now that we have discussed how Dijkstra’s Algorithm works and its time and space complexity, let’s look at how to implement it in Java. First, we need to define a few classes and methods.

We can start by defining a Node class which will represent each vertex in the graph. The Node class should contain two fields: an integer ID and a HashMap which will store the edges of the graph.

public class Node {
    int id;
    HashMap<Node, Integer> edges;
    //constructor and other methods
}

Next, we need to define a Graph class which will store the nodes of the graph. The Graph class should contain a HashMap which maps node IDs to Node objects.

public class Graph {
    HashMap<Integer, Node> nodes;
    //constructor and other methods
}

We also need to define a PriorityQueue class which will store the paths explored by the algorithm and the total cost of each path. The PriorityQueue class should contain a Comparator which will compare the cost of two paths.

public class PriorityQueue {
    Comparator<Path> comparator;
    //constructor and other methods
}

Finally, we need to define a Path class which will represent a path from one vertex to another. The Path class should contain two fields: a List of Nodes which will store the nodes in the path and an integer which will store the total cost of the path.

public class Path {
    List<Node> nodes;
    int cost;
    //constructor and other methods
}

Now that we have defined the necessary classes, we can start implementing the algorithm. We can start by initializing the graph with the nodes and edges.

Graph graph = new Graph();
//Add nodes to graph
//Add edges to graph

Next, we need to initialize the priority queue with the starting path. The starting path should contain only the starting node and have a cost of 0.

PriorityQueue queue = new PriorityQueue();
Path startPath = new Path();
startPath.nodes.add(graph.nodes.get(start));
startPath.cost = 0;
queue.add(startPath);

We can then start looping through the queue until it is empty. In each loop, we need to take the path with the lowest cost from the queue, explore all the edges from the last node in the path, and add the paths to the queue.

while(!queue.isEmpty()) {
    Path currPath = queue.poll();
    //Explore all edges from the last node in the path
    Node lastNode = currPath.nodes.get(currPath.nodes.size() - 1);
    for(Node neighbor : lastNode.edges.keySet()) {
        //Calculate cost of the path
        int cost = currPath.cost + lastNode.edges.get(neighbor);
        //Create a new path
        Path newPath = new Path();
        newPath.nodes.addAll(currPath.nodes);
        newPath.nodes.add(neighbor);
        newPath.cost = cost;
        //Add the new path to the queue
        queue.add(newPath);
    }
}

Once the priority queue is empty, the algorithm is complete and we will have found the shortest path from the starting vertex to every other vertex.

Here is another implementation of Dijkstra’s Algorithm in Java using an adjacency matrix. The following code example shows how to create an adjacency matrix and use it to find the shortest path between two nodes in a graph.

import java.util.ArrayList;
import java.util.List;
public class DijkstraAlgorithm {
  // Create an adjacency matrix
  int[][] adjMatrix;
  // Create a list of visited nodes
  List<Integer> visited = new ArrayList<>();
  // Create a list of unvisited nodes
  List<Integer> unvisited = new ArrayList<>();
  // Create an array to store distances
  int[] distances;
  // Create a variable to store the starting node
  int startNode;
  // Create a variable to store the destination node
  int destNode;
 
  public DijkstraAlgorithm(int[][] adjMatrix, int startNode, int destNode) {
    this.adjMatrix = adjMatrix;
    this.startNode = startNode;
    this.destNode = destNode;
    this.distances = new int[adjMatrix.length];
 
    // Set all distances to infinity
    for (int i = 0; i < distances.length; i++) {
      distances[i] = Integer.MAX_VALUE;
    }
 
    // Set the distance of the start node to 0
    distances[startNode] = 0;
 
    // Add all nodes to the unvisited list
    for (int i = 0; i < adjMatrix.length; i++) {
      unvisited.add(i);
    }
  }
 
  public void findShortestPath() {
    // Get the node with the smallest distance
    int minNode = getMinNode();
 
    // If the minNode is the destination node, we have found the shortest path
    if (minNode == destNode) {
      return;
    }
 
    // Move the minNode from the unvisited list to the visited list
    visited.add(minNode);
    unvisited.remove(minNode);
 
    // Check all adjacent nodes of the minNode
    for (int i = 0; i < adjMatrix.length; i++) {
      // If the adjacent node is not visited and the edge weight is not 0
      if (!visited.contains(i) && adjMatrix[minNode][i] != 0) {
        // Calculate the distance of the adjacent node
        int newDistance = distances[minNode] + adjMatrix[minNode][i];
        // If the new distance is less than the current distance, update it
        if (newDistance < distances[i]) {
          distances[i] = newDistance;
        }
      }
    }
 
    // Repeat the process until the destination node is reached
    findShortestPath();
  }
 
  // Find the node with the smallest distance
  private int getMinNode() {
    int minNode = 0;
    int minDistance = Integer.MAX_VALUE;
    for (int i = 0; i < distances.length; i++) {
      if (unvisited.contains(i) && distances[i] < minDistance) {
        minNode = i;
        minDistance = distances[i];
      }
    }
    return minNode;
  }
 
  // Print the distance of each node
  public void printDistances() {
    for (int i = 0; i < distances.length; i++) {
      System.out.println("Distance of node " + i + ": " + distances[i]);
    }
  }
 
  public static void main(String[] args) {
    int[][] adjMatrix = {
      {0, 8, 0, 3},
      {0, 0, 2, 5},
      {0, 0, 0, 4},
      {0, 0, 0, 0}
    };
    DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(adjMatrix, 0, 3);
    dijkstra.findShortestPath();
    dijkstra.printDistances();
  }
}

Conclusion

In this article, we discussed Dijkstra’s Algorithm and how to implement it in Java. Dijkstra’s Algorithm is a powerful algorithm used in graph theory to find the shortest path between two vertices. It has a time complexity of O(V^2 + E) and a space complexity of O(V), where V is the number of vertices and E is the number of edges in the graph. We discussed how the algorithm works and then looked at how to implement it in Java.

Exercises

Write a Java program to implement Dijkstra’s Algorithm using an adjacency list.

import java.util.ArrayList;
import java.util.List;
public class DijkstraAlgorithm {
  // Create an adjacency list
  List<List<int[]>> adjList;
  // Create a list of visited nodes
  List<Integer> visited = new ArrayList<>();
  // Create a list of unvisited nodes
  List<Integer> unvisited = new ArrayList<>();
  // Create an array to store distances
  int[] distances;
  // Create a variable to store the starting node
  int startNode;
  // Create a variable to store the destination node
  int destNode;
 
  public DijkstraAlgorithm(List<List<int[]>> adjList, int startNode, int destNode) {
    this.adjList = adjList;
    this.startNode = startNode;
    this.destNode = destNode;
    this.distances = new int[adjList.size()];
 
    // Set all distances to infinity
    for (int i = 0; i < distances.length; i++) {
      distances[i] = Integer.MAX_VALUE;
    }
 
    // Set the distance of the start node to 0
    distances[startNode] = 0;
 
    // Add all nodes to the unvisited list
    for (int i = 0; i < adjList.size(); i++) {
      unvisited.add(i);
    }
  }
 
  public void findShortestPath() {
    // Get the node with the smallest distance
    int minNode = getMinNode();
 
    // If the minNode is the destination node, we have found the shortest path
    if (minNode == destNode) {
      return;
    }
 
    // Move the minNode from the unvisited list to the visited list
    visited.add(minNode);
    unvisited.remove(minNode);
 
    // Check all adjacent nodes of the minNode
    for (int[] pair : adjList.get(minNode)) {
      // If the adjacent node is not visited
      if (!visited.contains(pair[0])) {
        // Calculate the distance of the adjacent node
        int newDistance = distances[minNode] + pair[1];
        // If the new distance is less than the current distance, update it
        if (newDistance < distances[pair[0]]) {
          distances[pair[0]] = newDistance;
        }
      }
    }
 
    // Repeat the process until the destination node is reached
    findShortestPath();
  }
 
  // Find the node with the smallest distance
  private int getMinNode() {
    int minNode = 0;
    int minDistance = Integer.MAX_VALUE;
    for (int i = 0; i < distances.length; i++) {
      if (unvisited.contains(i) && distances[i] < minDistance) {
        minNode = i;
        minDistance = distances[i];
      }
    }
    return minNode;
  }
 
  // Print the distance of each node
  public void printDistances() {
    for (int i = 0; i < distances.length; i++) {
      System.out.println("Distance of node " + i + ": " + distances[i]);
    }
  }
 
  public static void main(String[] args) {
    List<List<int[]>> adjList = new ArrayList<>();
 
    // Add edges to the adjacency list
    adjList.add(List.of(new int[] {1, 8}, new int[] {3, 3}));
    adjList.add(List.of(new int[] {2, 2}, new int[] {3, 5}));
    adjList.add(List.of(new int[] {3, 4}));
 
    DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(adjList, 0, 3);
    dijkstra.findShortestPath();
    dijkstra.printDistances();
  }
}

Write a Java program to implement Dijkstra’s Algorithm using a priority queue.

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
public class DijkstraAlgorithm {
  // Create an adjacency matrix
  int[][] adjMatrix;
  // Create a list of visited nodes
  List<Integer> visited = new ArrayList<>();
  // Create a priority queue to store unvisited nodes
  Queue<int[]> unvisited = new PriorityQueue<>((a, b) -> a[1] - b[1]);
  // Create an array to store distances
  int[] distances;
  // Create a variable to store the starting node
  int startNode;
  // Create a variable to store the destination node
  int destNode;
 
  public DijkstraAlgorithm(int[][] adjMatrix, int startNode, int destNode) {
    this.adjMatrix = adjMatrix;
    this.startNode = startNode;
    this.destNode = destNode;
    this.distances = new int[adjMatrix.length];
 
    // Set all distances to infinity
    for (int i = 0; i < distances.length; i++) {
      distances[i] = Integer.MAX_VALUE;
    }
 
    // Set the distance of the start node to 0
    distances[startNode] = 0;
 
    // Add all nodes to the unvisited priority queue
    for (int i = 0; i < adjMatrix.length; i++) {
      unvisited.add(new int[] {i, distances[i]});
    }
  }
 
  public void findShortestPath() {
    // Get the node with the smallest distance
    int minNode = getMinNode();
 
    // If the minNode is the destination node, we have found the shortest path
    if (minNode == destNode) {
      return;
    }
 
    // Move the minNode from the unvisited list to the visited list
    visited.add(minNode);
 
    // Check all adjacent nodes of the minNode
    for (int i = 0; i < adjMatrix.length; i++) {
      // If the adjacent node is not visited and the edge weight is not 0
      if (!visited.contains(i) && adjMatrix[minNode][i] != 0) {
        // Calculate the distance of the adjacent node
        int newDistance = distances[minNode] + adjMatrix[minNode][i];
        // If the new distance is less than the current distance, update it
        if (newDistance < distances[i]) {
          distances[i] = newDistance;
          unvisited.add(new int[] {i, distances[i]});
        }
      }
    }
 
    // Repeat the process until the destination node is reached
    findShortestPath();
  }
 
  // Find the node with the smallest distance
  private int getMinNode() {
    int minNode = unvisited.peek()[0];
    unvisited.poll();
    return minNode;
  }
 
  // Print the distance of each node
  public void printDistances() {
    for (int i = 0; i < distances.length; i++) {
      System.out.println("Distance of node " + i + ": " + distances[i]);
    }
  }
 
  public static void main(String[] args) {
    int[][] adjMatrix = {
      {0, 8, 0, 3},
      {0, 0, 2, 5},
      {0, 0, 0, 4},
      {0, 0, 0, 0}
    };
    DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(adjMatrix, 0, 3);
    dijkstra.findShortestPath();
    dijkstra.printDistances();
  }
}

What is the time complexity of Dijkstra’s Algorithm?

Create a graph with 5 vertices and 7 edges and implement Dijkstra’s Algorithm to find the shortest path between two nodes.

class Graph { 
 
    // A List of Lists to represent an adjacency list 
    List<List<Node>> adjList = null; 
  
    // Constructor 
    Graph(List<Edge> edges, int N) 
    { 
        adjList = new ArrayList<>(N); 
  
        for (int i = 0; i < N; i++) { 
            adjList.add(i, new ArrayList<>()); 
        } 
  
        // add edges to the undirected graph 
        for (Edge edge : edges) { 
            adjList.get(edge.src).add(edge.dest); 
            adjList.get(edge.dest).add(edge.src); 
        } 
    } 
  
    // Dijkstra's Algorithm 
    public void dijkstra(int src, int N) 
    { 
        // create a priority queue to store nodes and their 
        // distance from the source node 
        PriorityQueue<Node> pq = new PriorityQueue<>(N, 
                         (a, b) -> Integer.compare(a.cost, b.cost)); 
  
        // create an array to store the shortest distance 
        // from the source node to each node 
        int[] dist = new int[N]; 
  
        // initialize the distance array 
        Arrays.fill(dist, Integer.MAX_VALUE); 
        dist[src] = 0; 
  
        // add the source node to the priority queue 
        pq.add(new Node(src, 0)); 
  
        // loop until the priority queue is empty 
        while (!pq.isEmpty()) { 
            // get the node with the smallest distance 
            Node node = pq.poll(); 
  
            // explore the adjacent nodes of the current node 
            List<Node> adjNodes = adjList.get(node.vertex); 
            for (Node adjNode : adjNodes) { 
                // calculate the distance of the adjacent node 
                int newDist = dist[node.vertex] + adjNode.cost; 
  
                // if the new distance is smaller than the current distance 
                // update the distance and add the adjacent node to the priority queue 
                if (dist[adjNode.vertex] > newDist) { 
                    dist[adjNode.vertex] = newDist; 
                    pq.add(new Node(adjNode.vertex, newDist)); 
                } 
            } 
        } 
  
        // print the shortest distances stored in dist[] 
        printSolution(dist, N); 
    } 
  
    // Helper function to print the solution 
    public void printSolution(int[] dist, int N) 
    { 
        System.out.println("Vertex Distance from Source"); 
        for (int i = 0; i < N; ++i) 
            System.out.println(i + "\t\t" + dist[i]); 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        // input: 5 vertices and 7 edges 
        int N = 5; 
        List<Edge> edges = Arrays.asList( 
            new Edge(0, 1, 9), new Edge(1, 2, 10), 
            new Edge(0, 4, 15), new Edge(2, 4, 11), 
            new Edge(3, 2, 6), new Edge(1, 3, 7), 
            new Edge(3, 4, 9)); 
  
        // construct graph 
        Graph graph = new Graph(edges, N); 
  
        // Run Dijkstra's Algorithm from vertex 0 
        graph.dijkstra(0, N); 
    } 
} 

class Edge { 
    int src, dest, cost; 
  
    public Edge(int src, int dest, int cost) 
    { 
        this.src = src; 
        this.dest = dest; 
        this.cost = cost; 
    } 
} 

class Node { 
    int vertex, cost; 
  
    public Node(int vertex, int cost) 
    { 
        this.vertex = vertex; 
        this.cost = cost; 
    } 
}

Create a graph with 8 vertices and 12 edges and implement Dijkstra’s Algorithm to find the shortest path between two nodes.

class Graph { 
 
    // A List of Lists to represent an adjacency list 
    List<List<Node>> adjList = null; 
  
    // Constructor 
    Graph(List<Edge> edges, int N) 
    { 
        adjList = new ArrayList<>(N); 
  
        for (int i = 0; i < N; i++) { 
            adjList.add(i, new ArrayList<>()); 
        } 
  
        // add edges to the undirected graph 
        for (Edge edge : edges) { 
            adjList.get(edge.src).add(edge.dest); 
            adjList.get(edge.dest).add(edge.src); 
        } 
    } 
  
    // Dijkstra's Algorithm 
    public void dijkstra(int src, int N) 
    { 
        // create a priority queue to store nodes and their 
        // distance from the source node 
        PriorityQueue<Node> pq = new PriorityQueue<>(N, 
                         (a, b) -> Integer.compare(a.cost, b.cost)); 
  
        // create an array to store the shortest distance 
        // from the source node to each node 
        int[] dist = new int[N]; 
  
        // initialize the distance array 
        Arrays.fill(dist, Integer.MAX_VALUE); 
        dist[src] = 0; 
  
        // add the source node to the priority queue 
        pq.add(new Node(src, 0)); 
  
        // loop until the priority queue is empty 
        while (!pq.isEmpty()) { 
            // get the node with the smallest distance 
            Node node = pq.poll(); 
  
            // explore the adjacent nodes of the current node 
            List<Node> adjNodes = adjList.get(node.vertex); 
            for (Node adjNode : adjNodes) { 
                // calculate the distance of the adjacent node 
                int newDist = dist[node.vertex] + adjNode.cost; 
  
                // if the new distance is smaller than the current distance 
                // update the distance and add the adjacent node to the priority queue 
                if (dist[adjNode.vertex] > newDist) { 
                    dist[adjNode.vertex] = newDist; 
                    pq.add(new Node(adjNode.vertex, newDist)); 
                } 
            } 
        } 
  
        // print the shortest distances stored in dist[] 
        printSolution(dist, N); 
    } 
  
    // Helper function to print the solution 
    public void printSolution(int[] dist, int N) 
    { 
        System.out.println("Vertex Distance from Source"); 
        for (int i = 0; i < N; ++i) 
            System.out.println(i + "\t\t" + dist[i]); 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        // input: 8 vertices and 12 edges 
        int N = 8; 
        List<Edge> edges = Arrays.asList( 
            new Edge(0, 1, 8), new Edge(1, 2, 10), 
            new Edge(2, 3, 3), new Edge(3, 4, 6), 
            new Edge(4, 5, 7), new Edge(5, 6, 9), 
            new Edge(6, 7, 5), new Edge(7, 0, 4), 
            new Edge(1, 4, 15), new Edge(2, 5, 11), 
            new Edge(3, 6, 6), new Edge(4, 7, 9)); 
  
        // construct graph 
        Graph graph = new Graph(edges, N); 
  
        // Run Dijkstra's Algorithm from vertex 0 
        graph.dijkstra(0, N); 
    } 
} 

class Edge { 
    int src, dest, cost; 
  
    public Edge(int src, int dest, int cost) 
    { 
        this.src = src; 
        this.dest = dest; 
        this.cost = cost; 
    } 
} 

class Node { 
    int vertex, cost; 
  
    public Node(int vertex, int cost) 
    { 
        this.vertex = vertex; 
        this.cost = cost; 
    } 
}

Data Structures and Algorithms with Java

Participants 433