InterviewCodes/DijkstraAlgorithm.java at main · Tiwarishashwat/InterviewCodes · GitHub

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


//User function Template for Java


classSolution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
staticint[] dijkstra(intV, ArrayList<ArrayList<ArrayList<Integer>>> adj, intS)
 {
// Write your code here
// [node, dist]
PriorityQueue<int[]> pq = newPriorityQueue<>(newComparator<int[]>(){
publicintcompare(intp1[], intp2[]){
returnp1[1] - p2[1];
 }
 });
intdist[] = newint[V];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[S] = 0;
pq.offer(newint[]{S,0});
while(!pq.isEmpty()){
intpair[] = pq.poll();
intu = pair[0];
intd = pair[1];
if(d > dist[u]) continue;
for(ArrayList<Integer> neighbour : adj.get(u)){
intv = neighbour.get(0);
intw = neighbour.get(1);
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
pq.offer(newint[]{v,dist[v]});
 }
 }

 }
returndist;
 }
}
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


//User function Template for Java


classSolution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
staticint[] dijkstra(intV, ArrayList<ArrayList<ArrayList<Integer>>> adj, intS)
 {
// Write your code here
// [node, dist]
PriorityQueue<int[]> pq = newPriorityQueue<>(newComparator<int[]>(){
publicintcompare(intp1[], intp2[]){
returnp1[1] - p2[1];
 }
 });
intdist[] = newint[V];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[S] = 0;
pq.offer(newint[]{S,0});
while(!pq.isEmpty()){
intpair[] = pq.poll();
intu = pair[0];
intd = pair[1];
if(d > dist[u]) continue;
for(ArrayList<Integer> neighbour : adj.get(u)){
intv = neighbour.get(0);
intw = neighbour.get(1);
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
pq.offer(newint[]{v,dist[v]});
 }
 }

 }
returndist;
 }
}
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


//User function Template for Java


classSolution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
staticint[] dijkstra(intV, ArrayList<ArrayList<ArrayList<Integer>>> adj, intS)
 {
// Write your code here
// [node, dist]
PriorityQueue<int[]> pq = newPriorityQueue<>(newComparator<int[]>(){
publicintcompare(intp1[], intp2[]){
returnp1[1] - p2[1];
 }
 });
intdist[] = newint[V];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[S] = 0;
pq.offer(newint[]{S,0});
while(!pq.isEmpty()){
intpair[] = pq.poll();
intu = pair[0];
intd = pair[1];
if(d > dist[u]) continue;
for(ArrayList<Integer> neighbour : adj.get(u)){
intv = neighbour.get(0);
intw = neighbour.get(1);
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
pq.offer(newint[]{v,dist[v]});
 }
 }

 }
returndist;
 }
}
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


//User function Template for Java


classSolution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
staticint[] dijkstra(intV, ArrayList<ArrayList<ArrayList<Integer>>> adj, intS)
 {
// Write your code here
// [node, dist]
PriorityQueue<int[]> pq = newPriorityQueue<>(newComparator<int[]>(){
publicintcompare(intp1[], intp2[]){
returnp1[1] - p2[1];
 }
 });
intdist[] = newint[V];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[S] = 0;
pq.offer(newint[]{S,0});
while(!pq.isEmpty()){
intpair[] = pq.poll();
intu = pair[0];
intd = pair[1];
if(d > dist[u]) continue;
for(ArrayList<Integer> neighbour : adj.get(u)){
intv = neighbour.get(0);
intw = neighbour.get(1);
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
pq.offer(newint[]{v,dist[v]});
 }
 }

 }
returndist;
 }
}
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


//User function Template for Java


classSolution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
staticint[] dijkstra(intV, ArrayList<ArrayList<ArrayList<Integer>>> adj, intS)
 {
// Write your code here
// [node, dist]
PriorityQueue<int[]> pq = newPriorityQueue<>(newComparator<int[]>(){
publicintcompare(intp1[], intp2[]){
returnp1[1] - p2[1];
 }
 });
intdist[] = newint[V];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[S] = 0;
pq.offer(newint[]{S,0});
while(!pq.isEmpty()){
intpair[] = pq.poll();
intu = pair[0];
intd = pair[1];
if(d > dist[u]) continue;
for(ArrayList<Integer> neighbour : adj.get(u)){
intv = neighbour.get(0);
intw = neighbour.get(1);
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
pq.offer(newint[]{v,dist[v]});
 }
 }

 }
returndist;
 }
}
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


//User function Template for Java


classSolution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
staticint[] dijkstra(intV, ArrayList<ArrayList<ArrayList<Integer>>> adj, intS)
 {
// Write your code here
// [node, dist]
PriorityQueue<int[]> pq = newPriorityQueue<>(newComparator<int[]>(){
publicintcompare(intp1[], intp2[]){
returnp1[1] - p2[1];
 }
 });
intdist[] = newint[V];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[S] = 0;
pq.offer(newint[]{S,0});
while(!pq.isEmpty()){
intpair[] = pq.poll();
intu = pair[0];
intd = pair[1];
if(d > dist[u]) continue;
for(ArrayList<Integer> neighbour : adj.get(u)){
intv = neighbour.get(0);
intw = neighbour.get(1);
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
pq.offer(newint[]{v,dist[v]});
 }
 }

 }
returndist;
 }
}
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


//User function Template for Java


classSolution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
staticint[] dijkstra(intV, ArrayList<ArrayList<ArrayList<Integer>>> adj, intS)
 {
// Write your code here
// [node, dist]
PriorityQueue<int[]> pq = newPriorityQueue<>(newComparator<int[]>(){
publicintcompare(intp1[], intp2[]){
returnp1[1] - p2[1];
 }
 });
intdist[] = newint[V];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[S] = 0;
pq.offer(newint[]{S,0});
while(!pq.isEmpty()){
intpair[] = pq.poll();
intu = pair[0];
intd = pair[1];
if(d > dist[u]) continue;
for(ArrayList<Integer> neighbour : adj.get(u)){
intv = neighbour.get(0);
intw = neighbour.get(1);
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
pq.offer(newint[]{v,dist[v]});
 }
 }

 }
returndist;
 }
}
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


//User function Template for Java


classSolution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
staticint[] dijkstra(intV, ArrayList<ArrayList<ArrayList<Integer>>> adj, intS)
 {
// Write your code here
// [node, dist]
PriorityQueue<int[]> pq = newPriorityQueue<>(newComparator<int[]>(){
publicintcompare(intp1[], intp2[]){
returnp1[1] - p2[1];
 }
 });
intdist[] = newint[V];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[S] = 0;
pq.offer(newint[]{S,0});
while(!pq.isEmpty()){
intpair[] = pq.poll();
intu = pair[0];
intd = pair[1];
if(d > dist[u]) continue;
for(ArrayList<Integer> neighbour : adj.get(u)){
intv = neighbour.get(0);
intw = neighbour.get(1);
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
pq.offer(newint[]{v,dist[v]});
 }
 }

 }
returndist;
 }
}