Created
April 19, 2021 05:46
-
-
Save nil96/aa1c96957ff5e6b450d778581628c24e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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