This is my code please tell what is problem in my code and correct

#1

import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t!=0) {
int vtx=sc.nextInt();
int edge=sc.nextInt();
int graph[][]=new int[vtx+1][vtx+1];
for(int i=0;i<edge;i++) {
int row=sc.nextInt();
int col=sc.nextInt();
int w=sc.nextInt();
graph[row][col]=w;
graph[col][row]=w;
}
int src=sc.nextInt();
dijistra(graph,src);
t–;
}
}

private static void dijistra(int[][] graph, int src) {
	int []dist=new int[graph.length]; 
	boolean []visited=new boolean[graph.length];
	for(int i=0;i<graph.length;i++) {
		dist[i]=Integer.MAX_VALUE;
		visited[i]=false;
	}
	dist[src]=0;
	for(int i=1;i<graph.length;i++) {
		int min=findmin(dist,visited);
		visited[min]=true;
		for(int j=1;j<graph.length;j++) {
			if (!visited[j] && graph[min][j] != 0 && 
	dist[min] != Integer.MAX_VALUE && dist[min] + graph[min][j] < dist[j]) 
                dist[j] = dist[min] + graph[min][j]; 
		}
	}
	for(int i=1;i<graph.length;i++) {
		if(dist[i]!=0 && dist[i]!=Integer.MAX_VALUE) {
			System.out.print(dist[i]+" ");
		}
	}
	for(int i=1;i<graph.length;i++) {
		if(dist[i]==Integer.MAX_VALUE) {
			System.out.print(-1+" ");
		}
	}
}

private static int findmin(int[] dist, boolean[] visited) {
	int min=Integer.MAX_VALUE; int min_inx=-1;
	for(int i=0;i<dist.length;i++) {
		if(visited[i]==false && dist[i]<=min) {
			min=dist[i];
			min_inx=i;
		}
	}
	return min_inx;
}

}

#2

This problem is formally called Single Source Shortest Path problem.

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.

1 Like