Please check my code

#1 
import java.util.*;
public class Main {
static class Pair implements Comparable<Pair>{
	int vtx;
	int cost;
	@Override
	public int compareTo(Pair o){
		return o.cost-this.cost;
	}
}
static void dijkstra(HashMap<Integer,Vertices> vtces, int src){
	HashMap<Integer,Integer> ans=new HashMap<Integer,Integer>();
	PriorityQueue<Pair> pq=new PriorityQueue<Pair>();
	HashMap<Integer,Pair> map=new HashMap<>();
	for(int key:vtces.keySet()){
		Pair np=new Pair();
		np.vtx=key;
		np.cost=Integer.MAX_VALUE;
		if(key==src){
			np.cost=0;
		}
		//System.out.println(np.cost);
		pq.add(np);
		map.put(key,np);
	}
	while(!pq.isEmpty()){
		Pair rp=pq.poll();
		
		ans.put(rp.vtx,rp.cost);
		map.remove(rp.vtx);
		Set<Integer> adjs=vtces.get(rp.vtx).adj.keySet();
		for(int nbr:adjs){
			if(map.containsKey(nbr)){
				int oc=map.get(nbr).cost;
				int nc=rp.cost+vtces.get(rp.vtx).adj.get(nbr);
				if(nc<oc){
					Pair temp=map.get(nbr);
					temp.cost=nc;
					map.put(nbr,temp);
					pq.add(temp);
				}
			}

		}
	}
	for(int key:vtces.keySet()){
		if(ans.containsKey(key)){
			System.out.print(ans.get(key)+" ");

		}
		else{
			System.out.print("-1 ");
		}
	}



}
static class Vertices{
	HashMap<Integer,Integer> adj=new HashMap<Integer,Integer>();
}
public static void main(String args[]) {
	Scanner sc=new Scanner(System.in);
	int t=sc.nextInt();
	while(t-->0){
		int n=sc.nextInt();
		int e=sc.nextInt();
		HashMap<Integer,Vertices> vtces=new HashMap<Integer,Vertices>();
		for(int i=1;i<=n;i++){
			vtces.put(i,new Vertices());

			
		}
		while(e-->0){
			int u=sc.nextInt();
			int v=sc.nextInt();
			int wt=sc.nextInt();
			Vertices vtx1=vtces.get(u);
			Vertices vtx2=vtces.get(v);
			vtx1.adj.put(v,wt);
			vtx2.adj.put(u,wt);
		}
		int src=sc.nextInt();
		dijkstra(vtces,src);
		System.out.println();


	}

}

}

#2

In this problem, for a given graph G with N vertices, M undirected edges with integer weights between them, and special vertex S, the goal is to find the length of the shortest paths from S to each of all N vertices.

If all edges of G have non-negative weights, the most well-known and also widely used method of solving this problem is to use Dijkstra’s algorithm implemented with a priority queue. In that case, the total time complexity of the algorithm is O(MlogN). This is true because each edge of the graph is examined exactly once, and such an examination can cause a constant number of updates in a priority queue containing either O(N) or O(M) vertices depending on the implementation. However, since each such operation on a priority queue has complexity proportional to the logarithm of its size, it does not matter if the queue contains O(N) or O(M) entries, since logM <= 2logN because M is at most N2 in this problem.

Try to use arrays instead of maps.

#3

what’s the wrong in my code??

#4 
  // I am getting Wrong Answer 
import java.util.*;
public class Main {
static class Pair implements Comparable<Pair>{
	int vtx;
	int cost;
	@Override
	public int compareTo(Pair o){
		 if(this.cost-o.cost>0)
		 return 1;
		 return -1;
	}
	
}
static void dijkstra(int mat[][], int src){
	HashMap<Integer,Integer> ans=new HashMap<Integer,Integer>();
	PriorityQueue<Pair> pq=new PriorityQueue<Pair>();
	HashMap<Integer,Pair> map=new HashMap<>();
	for(int key=1;key<mat.length;key++){
		Pair np=new Pair();
		np.vtx=key;
		np.cost=Integer.MAX_VALUE;
		if(key==src){
			np.cost=0;
		}

		pq.add(np);
		map.put(key,np);
	}
	while(!pq.isEmpty()){
		Pair rp=pq.poll();
		if(rp.cost>0)
		ans.put(rp.vtx,rp.cost);
		map.remove(rp.vtx);
	
		for(int nbr=1;nbr<mat[rp.vtx].length;nbr++){
			if(mat[rp.vtx][nbr]!=0&&nbr!=src&& map.containsKey(nbr)){
				int oc=map.get(nbr).cost;
				int nc=rp.cost+mat[rp.vtx][nbr];
				if(nc<oc){
					Pair temp=map.get(nbr);
					temp.cost=nc;
					map.put(nbr,temp);
					pq.add(temp);
				}
		
			}

		}
	}
//	System.out.println(ans);
	for(int key=1;key<mat.length;key++){
		if(ans.containsKey(key)&&key!=src&&ans.get(key)!=Integer.MAX_VALUE){
			System.out.print(ans.get(key)+" ");

		}
		else if(key!=src){
			System.out.print("-1 ");
		}
	}



}


public static void main(String args[]) {
	Scanner sc=new Scanner(System.in);
	int t=sc.nextInt();
	while(t-->0){
		int n=sc.nextInt();
		int e=sc.nextInt();
		int mat[][]=new int[n+1][n+1];
		while(e-->0){
			int u=sc.nextInt();
			int v=sc.nextInt();
			int wt=sc.nextInt();
			
			mat[v][u]=wt;
			mat[u][v]=wt;
		}
		int src=sc.nextInt();
		dijkstra(mat,src);
		System.out.println();


	}

}
}

#5

try for this input :
1
20 54
1 7 45
2 14 15
3 7 29
4 1 48
5 1 66
6 7 17
7 14 15
8 14 43
9 1 27
10 1 33
11 14 64
12 14 27
13 7 66
14 7 54
15 14 56
16 7 21
17 1 20
18 1 34
19 7 52
20 14 14
9 14 9
15 1 39
12 1 24
9 1 16
1 2 33
18 1 46
9 1 28
15 14 3
12 1 27
1 2 5
15 1 34
1 2 28
9 7 16
3 7 23
9 7 21
9 14 19
3 1 20
3 1 5
12 14 19
3 14 2
12 1 46
3 14 5
9 14 44
6 14 26
9 14 16
9 14 34
6 7 42
3 14 27
1 7 9
1 7 41
15 14 19
12 7 13
3 7 10
1 7 2
17
correct output : 20 25 25 68 86 39 22 70
you get: 20 48 25 68 86 64 22 95 43 53 116 35 88 52 54 43 66 74 66

#6

I am not able to rectify problem in my code , please check my code and tell me where i need to correct it

#7

Your implementation of Dijkstra Algo is wrong. In Dijkstra algorithm , you pick the node with the least distance and then work with its neighbour and proceed this way till all nodes are visited.
In your code, though you do mark the distance of source node as 0, your loop begins with 1 and goes till n
You visit each node in increasing order of their node values. The graph may not always be connected that way as in the testcase above. It may even be not connected at all. Implementing a simple loop as such will not work. Just use dijkstra algo on graph, either by lists or by adjacency matrix. By using hashmaps you are over complicating. This is a greedy algorithm. Make the according changes in your code.
refer to this

please mark your doubt as resolved and rate as well :slight_smile:

#8

but i am following same approach as given in video lecture

#9

okay let me check
please go through the approach discussed above too

#10

if graph is not connected for a node , then my code will print -1 for that because path is not exist for that, and your code is not using Min Heap(Priority Queue).

#11

yes use adjacency matrix

#12

this is the code as discussed in the video:


go through this

#13

i am also using adjacency matrix and hashmap is use instead of boolean array

#14

i am also using same approach