Calculate shortest paths in Java by implementing Dijkstra’s Algorithm

Conceived by Edsger W. Dijsktra in 1956 and published three years later, Dijkstra’s algorithm is a one of the most known algorithms for finding the shortest paths between nodes in a graph. This algorithm is applied in a lot of domains. For example, once you have represented road networks in a graph, it becomes easy to calculate shortest paths inside this graph by applying Dijkstra’s algorithm.

In Pseudocode, Dijkstra’s algorithm can be translated like that :

In this tutorial, you’re going to learn how to implement Disjkstra’s Algorithm in Java. In a first time, we need to create objects to represent a graph before to apply Dijkstra’s Algorithm.

1. Represent Edges

In a graph, Edges are used to link two Nodes. So, an Edge is linked to two nodes and have a length that is an integer here. It’s useful to represent a distance for example in road networks.

package com.ssaurel.dijsktra;

public class Edge {

  private int fromNodeIndex;
  private int toNodeIndex;
  private int length;

  public Edge(int fromNodeIndex, int toNodeIndex, int length) {
    this.fromNodeIndex = fromNodeIndex;
    this.toNodeIndex = toNodeIndex;
    this.length = length;
  }

  public int getFromNodeIndex() {
    return fromNodeIndex;
  }

  public int getToNodeIndex() {
    return toNodeIndex;
  }

  public int getLength() {
    return length;
  }

  // determines the neighbouring node of a supplied node, based on the two nodes connected by this edge
  public int getNeighbourIndex(int nodeIndex) {
    if (this.fromNodeIndex == nodeIndex) {
      return this.toNodeIndex;
    } else {
      return this.fromNodeIndex;
   }
  }

}

 

2. Represent Nodes

Now, it’s time to represent Nodes. A Node must have a list of Edge that are linked to it. Besides, it must have a field to define if the Node has been visited or no. It will be useful when we will apply Dijkstra’s Algorithm to calculate shortest paths in the graph. Last, we need to define a distanceFromSource field that will represent the result for that Node of the algorithm.

package com.ssaurel.dijsktra;

import java.util.ArrayList;

public class Node {

  private int distanceFromSource = Integer.MAX_VALUE;
  private boolean visited;
  private ArrayList<Edge> edges = new ArrayList<Edge>(); // now we must create edges

  public int getDistanceFromSource() {
    return distanceFromSource;
  }

  public void setDistanceFromSource(int distanceFromSource) {
    this.distanceFromSource = distanceFromSource;
  }

  public boolean isVisited() {
    return visited;
  }

  public void setVisited(boolean visited) {
    this.visited = visited;
  }

  public ArrayList<Edge> getEdges() {
    return edges;
  }

  public void setEdges(ArrayList<Edge> edges) {
    this.edges = edges;
  }

}

 

3. Represent a Graph

Now that we have Edges and Nodes, we can represent a Graph that must contain Edges and Nodes. In the constructor, we take an array of Edges and we build the Graph by creating corresponding Nodes. The Dijkstra’s Algorithm is implemented in the calculateShortestDistances() method. It’s really the application of the Pseudocode algorithm displayed previously. Our Graph class is like that :

package com.ssaurel.dijsktra;

import java.util.ArrayList;

// now we must create graph object and implement dijkstra algorithm
public class Graph {

  private Node[] nodes;
  private int noOfNodes;
  private Edge[] edges;
  private int noOfEdges;

  public Graph(Edge[] edges) {
    this.edges = edges;

    // create all nodes ready to be updated with the edges
    this.noOfNodes = calculateNoOfNodes(edges);
    this.nodes = new Node[this.noOfNodes];

    for (int n = 0; n < this.noOfNodes; n++) {
      this.nodes[n] = new Node();
    }

    // add all the edges to the nodes, each edge added to two nodes (to and from)
    this.noOfEdges = edges.length;

    for (int edgeToAdd = 0; edgeToAdd < this.noOfEdges; edgeToAdd++) {
      this.nodes[edges[edgeToAdd].getFromNodeIndex()].getEdges().add(edges[edgeToAdd]);
      this.nodes[edges[edgeToAdd].getToNodeIndex()].getEdges().add(edges[edgeToAdd]);
    }

  }

  private int calculateNoOfNodes(Edge[] edges) {
    int noOfNodes = 0;

    for (Edge e : edges) {
      if (e.getToNodeIndex() > noOfNodes)
        noOfNodes = e.getToNodeIndex();
      if (e.getFromNodeIndex() > noOfNodes)
        noOfNodes = e.getFromNodeIndex();
    }

    noOfNodes++;

    return noOfNodes;
  }

  // next video to implement the Dijkstra algorithm !!!
  public void calculateShortestDistances() {
    // node 0 as source
    this.nodes[0].setDistanceFromSource(0);
    int nextNode = 0;

    // visit every node
    for (int i = 0; i < this.nodes.length; i++) {
      // loop around the edges of current node
      ArrayList<Edge> currentNodeEdges = this.nodes[nextNode].getEdges();

      for (int joinedEdge = 0; joinedEdge < currentNodeEdges.size(); joinedEdge++) {
        int neighbourIndex = currentNodeEdges.get(joinedEdge).getNeighbourIndex(nextNode);

        // only if not visited
        if (!this.nodes[neighbourIndex].isVisited()) {
          int tentative = this.nodes[nextNode].getDistanceFromSource() + currentNodeEdges.get(joinedEdge).getLength();

          if (tentative < nodes[neighbourIndex].getDistanceFromSource()) {
            nodes[neighbourIndex].setDistanceFromSource(tentative);
          }
        }
      }

      // all neighbours checked so node visited
      nodes[nextNode].setVisited(true);

      // next node must be with shortest distance
      nextNode = getNodeShortestDistanced();

   }
  }

  // now we're going to implement this method in next part !
  private int getNodeShortestDistanced() {
    int storedNodeIndex = 0;
    int storedDist = Integer.MAX_VALUE;

    for (int i = 0; i < this.nodes.length; i++) {
      int currentDist = this.nodes[i].getDistanceFromSource();

      if (!this.nodes[i].isVisited() && currentDist < storedDist) {
        storedDist = currentDist;
        storedNodeIndex = i;
      }
    }

    return storedNodeIndex;
  }

  // display result
  public void printResult() {
    String output = "Number of nodes = " + this.noOfNodes;
    output += "\nNumber of edges = " + this.noOfEdges;

    for (int i = 0; i < this.nodes.length; i++) {
      output += ("\nThe shortest distance from node 0 to node " + i + " is " + nodes[i].getDistanceFromSource());
    }

    System.out.println(output);
  }

  public Node[] getNodes() {
    return nodes;
  }

  public int getNoOfNodes() {
    return noOfNodes;
  }

  public Edge[] getEdges() {
    return edges;
  }

  public int getNoOfEdges() {
    return noOfEdges;
  }

}

In the printResult() method, we have just to iterate on the Nodes’ array and display the distanceFromSource property value.

 

4. Assemble the puzzle in a Main class

Now, it’s time to test our implementation of the Dijkstra’s Algorithm. So, we consider the following graph :

 

We define that graph in our Main class and then we have just to call the calculateShortestDistances() method. Last, we need to print the result of the algorithm.

package com.ssaurel.dijsktra;

public class Main {

  public static void main(String[] args) {
    Edge[] edges = {
      new Edge(0, 2, 1), new Edge(0, 3, 4), new Edge(0, 4, 2),
      new Edge(0, 1, 3), new Edge(1, 3, 2), new Edge(1, 4, 3),
      new Edge(1, 5, 1), new Edge(2, 4, 1), new Edge(3, 5, 4),
      new Edge(4, 5, 2), new Edge(4, 6, 7), new Edge(4, 7, 2),
      new Edge(5, 6, 4), new Edge(6, 7, 5)
    };

    Graph g = new Graph(edges);
    g.calculateShortestDistances();
    g.printResult(); // let's try it !
  }

}

 

Result is detailed in the following figure.

Like you can see, our implementation works well !

 

5. Bonus

As a Bonus, you can enjoy the following tutorial in video :