CC-16 : Find shortest path between 2 vertices in a graph.

Description:

Given an input graph and two input vertices, find shortest path between the two input vertices.

Test cases and expected outputs:

Input Parameters	Expected outputs
GraphShortestPath gph= new GraphShortestPath(5); gph.addEdge(0, 1); gph.addEdge(0, 2); gph.addEdge(0, 3); gph.addEdge(0, 4); gph.addEdge(1, 2); gph.addEdge(2, 3); gph.addEdge(3, 4); gph.displayGraph(); retVal=gph.shortestPath(0,4); System.out.println("Shortest path between 0, 4: "+ retVal);	vertex 0->1->2->3->4 vertex 1->0->2 vertex 2->0->1->3 vertex 3->0->2->4 vertex 4->0->3 Shortest path between 0, 4: 1
gph= new GraphShortestPath(5); gph.addEdge(0, 1); gph.addEdge(1, 2); gph.addEdge(2, 3); gph.addEdge(3, 4); gph.displayGraph(); retVal=gph.shortestPath(0,4); System.out.println("Shortest path between 0, 4: "+ retVal);	vertex 0->1 vertex 1->0->2 vertex 2->1->3 vertex 3->2->4 vertex 4->3 Shortest path between 0, 4: 4

Pseudocode:

Initialize an int variable named vertices to store the number of vertices in the graph.

Initialize ArrayList of Arraylists to store the adjacencyLists.

Initialize an int variable named visited to store information whether a particular vertice in the graph has been visited.

shortestPath() method:

The method receives 2 input parameters named source and destination.

Initialize a LinkedList of int arrays named queue to hold the vertices to be processed.

While queue is not empty:

Extract int array named current from the queue.

Set int variable currentNode to current[0].

Set int variable named distance to current[1].

If (currentNode == destination):

Return distance.

If visited[currentNode] == 1, then:

Finish current iteration (go back to while statement).

Set visited[currentNode]=1.

Set Iterator itr to list of adjacent nodes of currentNode from the adjacencyLists.

Iterate through adjacent nodes of currentNode:

Set adjacentNode as currenty iterated node.

Add {adjacentNode, distance+1} to queue.

• Return -1 if there is no path from source to distance.

Code:

public class GraphShortestPath {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public GraphShortestPath(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 adjacencyLists.get(dest).add(source);
 }
 
 public int shortestPath(int source, int destination) {
    LinkedList<int[]> queue = new LinkedList<>();
     queue.add(new int[]{source, 0});

     while (!queue.isEmpty()) {
         int[] current = queue.poll();
         int currentNode = current[0];
         int distance = current[1];

         if (currentNode == destination) {
             return distance;
         }
         if (visited[currentNode]==1) {
             continue;
         }
        visited[currentNode]=1;
        Iterator<Integer> itr=adjacencyLists.get(currentNode).iterator();
        while (itr.hasNext()) {
        	int adjacentNode=itr.next();
            queue.add(new int[]{adjacentNode, distance + 1});
         }
     }
     return -1;
 }

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.*;


public class GraphShortestPath {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public GraphShortestPath(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 adjacencyLists.get(dest).add(source);
 }
 
 public int shortestPath(int source, int destination) {
    LinkedList<int[]> queue = new LinkedList<>();
     queue.add(new int[]{source, 0});

     while (!queue.isEmpty()) {
         int[] current = queue.poll();
         int currentNode = current[0];
         int distance = current[1];

         if (currentNode == destination) {
             return distance;
         }
         if (visited[currentNode]==1) {
             continue;
         }
        visited[currentNode]=1;
        Iterator<Integer> itr=adjacencyLists.get(currentNode).iterator();
        while (itr.hasNext()) {
        	int adjacentNode=itr.next();
            queue.add(new int[]{adjacentNode, distance + 1});
         }
     }
     return -1;
 }  
 
 public void displayGraph() {
	 for (int iIdx=0;iIdx< adjacencyLists.size();iIdx++) {
		 System.out.println();
		 System.out.print("vertex "+iIdx);
		 for (int jIdx=0;jIdx< adjacencyLists.get(iIdx).size();jIdx++) {
			 System.out.print("->"+adjacencyLists.get(iIdx).get(jIdx));
		 }
	 }
 }

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	GraphShortestPath gph=new GraphShortestPath(5);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.addEdge(0, 4);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.addEdge(3, 4);
	gph.displayGraph();
	retVal=gph.shortestPath(0,4);
	System.out.println();
	System.out.println("Shortest path betwee 0, 4: "+ retVal);
	
	gph=new GraphShortestPath(5);
	gph.addEdge(0, 1);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.addEdge(3, 4);
	gph.displayGraph();
	retVal=gph.shortestPath(0,4);
	System.out.println();
	System.out.println("Shortest path betwee 0, 4: "+ retVal);
	
	
	gph=new GraphShortestPath(5);
	gph.addEdge(0, 1);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.addEdge(3, 4);
	gph.addEdge(2, 4);
	gph.displayGraph();
	retVal=gph.shortestPath(2,4);
	System.out.println();
	System.out.println("Shortest path betwee 0, 4: "+ retVal);
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}