Please provide the source code and a readme file for a short description of your

Question

Please provide the source code and a readme file for a short description of your program.

Write a program to find a shortest path between any two vertices (from 'a' to 'l' in the following graph. You may use the DFS code in the class to start with and represent the graph using either adjacency matrix or adjacency list. The program should take two vertex's names (from 'a' to 'l') and print out the shortest path between them. For example, if the inputs are "a" and "g", then the shortest path should print as "a - b - c - g"; if the inputs are "b" and "k", then the shortest path should be "b - f - k". You need to implement the Breadth-first search (BFS) to create a BFS tree starting from one vertex and then you can find the shortest path between the root and any other vertex.

Explanation / Answer

//BFSShortestPath.java

/******************************************************************************
* Name : BFSShortestPath.java
* Author : sitaram.chhimpa
* Date : Apr 12, 2017
*****************************************************************************/

package sample;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/**
* @author Dany
*/
public class BFSShortestPath
{

public static Graph constructGraph()
{
int noOfVertices, noOfEdges;
Graph graph = null;

char u, v;
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext())
{
noOfVertices = scanner.nextInt();
noOfEdges = scanner.nextInt();

graph = new Graph(noOfVertices);
for (int i = 0; i < noOfEdges; i++)
{
u = scanner.next().charAt(0);
v = scanner.next().charAt(0);
graph.addEdge(u, v);
graph.addEdge(v, u);
}
break;
}
// graph.printGraph();
return graph;
}

/**
* doBFSShortestPath(G, s, t): L <- Empty visited <- Empty Q <- Empty S <- Empty Q <- add(Q, s) S <- add(S, s)
* visited[s] <- true while(!Empty(Q)) u <- poll(Q) for each vertex v in Adj[u] if visited[v]!=true Q <- add(Q,v) S
* <- add(S,v) visited[v] = true if u == dest break currentSrc=t L <- add(L,t) while(!Empty(S)) u <= poll(S) if
* isNeighbor(G,currentSrc,u) L <- add(L, u) currentSrc = node; if node == source break; return L
*
* @param graph
* @param source
* @param dest
* @return
*/

public static ArrayList<Character> doBFSShortestPath(Graph graph, char source, char dest)
{
ArrayList<Character> shortestPathList = new ArrayList<Character>();
HashMap<Character, Boolean> visited = new HashMap<Character, Boolean>();

if (source == dest)
{
return null;
}
Queue<Character> queue = new LinkedList<Character>();
Stack<Character> pathStack = new Stack<Character>();

queue.add(source);
pathStack.add(source);
visited.put(source, true);

while (!queue.isEmpty())
{
int u = queue.poll();
ArrayList<Character> adjList = graph.getOutEdges(u);

for (char v : adjList)
{
if (!visited.containsKey(v))
{
queue.add(v);
visited.put(v, true);
pathStack.add(v);
if (u == dest)
{
break;
}
}
}
}

// To find the path
char node, currentSrc = dest;
shortestPathList.add(dest);
while (!pathStack.isEmpty())
{
node = pathStack.pop();
if (graph.isNeighbor(currentSrc, node))
{
shortestPathList.add(node);
currentSrc = node;
if (node == source)
{
break;
}
}
}

return shortestPathList;
}

/**
* Method to find the shortest path
*/
public static void findShortestPath()
{

Graph graph = constructGraph();
Scanner scanner = new Scanner(System.in);
char source = scanner.next().charAt(0);
char dest = scanner.next().charAt(0);

ArrayList<Character> shortestPathList = doBFSShortestPath(graph, source, dest);

System.out.print("[ " + source + " ");
for (char node : shortestPathList)
{
System.out.print(node + " ");
}
System.out.print("]");
}

/**
* @param args
*/
public static void main(String[] args)
{
BFSShortestPath.findShortestPath();
}

}

//Graph.java

/******************************************************************************
* Name : Graph.java
* Author : sitaram.chhimpa
* Date : Apr 12, 2017
*****************************************************************************/

package sample;

import java.util.ArrayList;

/**
* @author Dinesh Appavoo
*/
public class Graph
{

public static ArrayList<Character>[] adjacencyList = null;
public int noOfVertices;

public Graph(int noOfVertices)
{
adjacencyList = new ArrayList[noOfVertices + 1];
this.noOfVertices = noOfVertices;
for (int i = 0; i < (noOfVertices + 1); i++)
{
adjacencyList[i] = new ArrayList<Character>();
}
}

/**
* @param u
* @param v
* @param w To add edges to the adjacency list in graph
*/
public void addEdge(char u, char v)
{
if (adjacencyList[Character.getNumericValue(u) % 10] == null)
{
adjacencyList[Character.getNumericValue(u) % 10] = new ArrayList<Character>();
}
adjacencyList[Character.getNumericValue(u) % 10].add(v);
}

/**
* @param u
* @param v To remove the edge from the graph
*/
public void removeEdge(int u, int v)
{
int indexToBeRemoved = -1;
ArrayList<Character> edgeList = adjacencyList[u];
for (int i = 0; i < adjacencyList[u].size(); i++)
{
int val = edgeList.get(i);
if (val == v)
{
indexToBeRemoved = i;
}
}
edgeList.remove(indexToBeRemoved);
}

/**
* Method to verify whether u and v are neighbors
*
* @param u
* @param v
* @return
*/
public boolean isNeighbor(int u, int v)
{
if (adjacencyList[Character.getNumericValue(u) % 10] == null)
{
return false;
}
return adjacencyList[Character.getNumericValue(u) % 10].contains(v);

}

/**
* Method to return the size of the graph
*
* @return
*/
public int size()
{
return adjacencyList.length;
}

/**
* @param u
* @return To return the outgoing edges for the given source
*/
public ArrayList<Character> getOutEdges(int u)
{
return adjacencyList[Character.getNumericValue(u) % 10];
}

/**
* Method to return the adjacency list
*
* @return
*/
public ArrayList<Character>[] getAdjacencyList()
{
return adjacencyList;
}

public void printGraph()
{
ArrayList<Character> edgeList;
for (int i = 1; i <= this.noOfVertices; i++)
{
edgeList = adjacencyList[i];
if (edgeList != null)
{
for (int v : edgeList)
{
System.out.println("u : " + i + " v : " + v);
}
}
}
}

/**
* @param args Main function to test the graph
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub

Graph graph = new Graph(3);
/*
* graph.addEdge(1, 2); graph.addEdge(1, 3); graph.addEdge(3, 1); graph.addEdge(2, 1); graph.addEdge(2, 3);
* graph.addEdge(3, 2);
*/
graph.printGraph();

}

}

Output:

12
14
a b a e b c b f c g d h e f e i f j f k g k h l i j k l
a l
[ a b f k l ]

If you not able to understand please let me know I will provide you explanation.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.