Skip to content

Instantly share code, notes, and snippets.

@nil96
Created April 19, 2021 05:46
Show Gist options
  • Save nil96/aa1c96957ff5e6b450d778581628c24e to your computer and use it in GitHub Desktop.
Save nil96/aa1c96957ff5e6b450d778581628c24e to your computer and use it in GitHub Desktop.
// Java program to find shortest path in an undirected
// graph
import java.util.*;
public class pathUnweighted {
static Map<String,Integer> mp = new HashMap<>();
static Map<Integer,String> rmp = new HashMap<>();
public static String GraphChallenge(String[] strArr) {
int n = Integer.parseInt(strArr[0]);
int v = n+1;
ArrayList<ArrayList<Integer>> adj =
new ArrayList<ArrayList<Integer>>(v);
for (int i = 0; i < v; i++) {
adj.add(new ArrayList<Integer>());
}
for(int i=1;i<=n;i++) {
mp.put(strArr[i],Integer.valueOf(i));
rmp.put(Integer.valueOf(i),strArr[i]);
}
// {"5","A","B","C","D","F","A-B","A-C","B-C","C-D","D-F"};
for(int i=n+1;i<strArr.length;i++){
String []nodes = strArr[i].split("-");
int src = mp.get(nodes[0]).intValue();
int dest = mp.get(nodes[1]).intValue();
addEdge(adj, src, dest);
}
int source = mp.get(strArr[1]).intValue();
int dest = mp.get(strArr[n]).intValue();
return printShortestDistance(adj, source, dest, v);
}
// Driver Program
public static void main(String args[])
{
Scanner s = new Scanner(System.in);
String[] s1 = {"9","Z","B","C","D","R","A","Y","Q","E","A-Z","A-R","Z-Y","Z-C","C-B","Y-Q","Q-D","D-E","R-E"};
String ans = GraphChallenge(s1);
System.out.println(ans);
}
// function to form edge between two vertices
// source and dest
private static void addEdge(ArrayList<ArrayList<Integer>> adj, int i, int j)
{
adj.get(i).add(j);
adj.get(j).add(i);
}
// function to print the shortest distance and path
// between source vertex and destination vertex
private static String printShortestDistance(
ArrayList<ArrayList<Integer>> adj,
int s, int dest, int v)
{
String ans="";
int pred[] = new int[v];
int dist[] = new int[v];
if (BFS(adj, s, dest, v, pred, dist) == false) {
// System.out.println("Given source and destination" +"are not connected");
ans = "-1";
return ans;
}
// LinkedList to store path
LinkedList<Integer> path = new LinkedList<Integer>();
int crawl = dest;
path.add(crawl);
while (pred[crawl] != -1) {
path.add(pred[crawl]);
crawl = pred[crawl];
}
// Print distance
// System.out.println("Shortest path length is: " + dist[dest]);
// Print path
// System.out.println("Path is ::");
for (int i = path.size() - 1; i > 0; i--) {
String test = rmp.get(path.get(i));
ans = ans + test + "-";
// System.out.print(path.get(i) + " ");
}
ans = ans + rmp.get(path.get(0));
return ans;
}
private static boolean BFS(ArrayList<ArrayList<Integer>> adj, int src,
int dest, int v, int pred[], int dist[])
{
LinkedList<Integer> queue = new LinkedList<Integer>();
boolean visited[] = new boolean[v];
for (int i = 0; i < v; i++) {
visited[i] = false;
dist[i] = Integer.MAX_VALUE;
pred[i] = -1;
}
visited[src] = true;
dist[src] = 0;
queue.add(src);
while (!queue.isEmpty()) {
int u = queue.remove();
for (int i = 0; i < adj.get(u).size(); i++) {
if (visited[adj.get(u).get(i)] == false) {
visited[adj.get(u).get(i)] = true;
dist[adj.get(u).get(i)] = dist[u] + 1;
pred[adj.get(u).get(i)] = u;
queue.add(adj.get(u).get(i));
// stopping condition (when we find
// our destination)
if (adj.get(u).get(i) == dest)
return true;
}
}
}
return false;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment