-
Notifications
You must be signed in to change notification settings - Fork 7
/
Copy pathShortest Path in Unweighted Graph
73 lines (56 loc) · 2.07 KB
/
Shortest Path in Unweighted Graph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class Main {
public static void main(String[] args) {
int noOfVertices = 7;
int startVertex=2; // C is start vertex
List<Integer>[] adj=new ArrayList[noOfVertices];
List<Integer> list=new ArrayList<>();
list.add(1);
list.add(3);
adj[0]=list;
list=new ArrayList<>();
list.add(3);
list.add(4);
adj[1]=list;
list=new ArrayList<>();
list.add(0);
list.add(5);
adj[2]=list;
list=new ArrayList<>();
list.add(5);
list.add(6);
adj[3]=list;
list=new ArrayList<>();
list.add(6);
adj[4]=list;
adj[5]=new ArrayList<>();
list=new ArrayList<>();
list.add(5);
adj[6]=list;
int[] path = new int[noOfVertices];
int[] distance = new int[noOfVertices];
Arrays.fill(distance,-1); // Intialize distance array
distance[startVertex]=0; // Making distance for start vertex 0
path[startVertex]=startVertex; // Updating path for start vertex to itself
Queue<Integer> q=new LinkedList<>();
q.add(startVertex);
while(!q.isEmpty()){
int size=q.size();
while(size-->0){
int vertex=q.remove();
List<Integer> adjVertices=adj[vertex];
for(Integer adjVertex: adjVertices){
if(distance[adjVertex]==-1){
distance[adjVertex]=distance[vertex]+1;
path[adjVertex]=vertex;
q.add(adjVertex);
}
}
}
}
System.out.println("Distance from "+(char)(startVertex+'A')+" :");
for(int i=0;i<noOfVertices; i++){
System.out.print("Distance to "+(char)(i+'A')+" is "+distance[i]);
System.out.println(" from path "+(char)(path[i]+'A'));
}
}
}