My code is having wrong test case.Below is the code:-
import java.util.Scanner;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Comparator;
public class Main {
public static void main(String args[]) {
Scanner scn = new Scanner(System.in);
int t = scn.nextInt();
while(t>0){
Graph graph = new Graph();
int n = scn.nextInt();
int m = scn.nextInt();
for(int i=1;i<=n;i++){
graph.addvertex(i);
}
while(m>0){
int a = scn.nextInt();
int b = scn.nextInt();
int cost = scn.nextInt();
graph.addedge(a,b,cost);
m–;
}
int src = scn.nextInt();
HashMap<Integer,Integer> ans = graph.dijkstra(src);
for(int i=1;i<=n;i++){
if(i!=src){
if(ans.get(i)==Integer.MAX_VALUE)
ans.put(i,-1);
System.out.print(ans.get(i)+" “);
}
}
System.out.println();
t–;
}
}
}
class Graph{
private class Vertex{
HashMap<Integer,Integer> nbrs = new HashMap<>();
}
HashMap<Integer,Vertex> vtces;
Graph(){
vtces = new HashMap<>();
}
public int numvertex(){
return this.vtces.size();
}
public boolean containsvertex(int vname){
return this.vtces.containsKey(vname);
}
public void addvertex(int vname){
if(vtces.containsKey(vname)){
return;
}
Vertex vtx = new Vertex();
vtces.put(vname,vtx);
}
public void removevertex(int vname){
Vertex vtx = vtces.get(vname);
ArrayList keys = new ArrayList<>(vtx.nbrs.keySet());
for(int key : keys){
Vertex nbrvtx = vtces.get(key);
nbrvtx.nbrs.remove(vname);
}
}
public int numedges(){
int count=0;
ArrayList keys = new ArrayList<>(vtces.keySet());
for(int key : keys){
Vertex vtx = vtces.get(key);
count+=vtx.nbrs.size();
}
return count/2;
}
public boolean containsedge(int vname1,int vname2){
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if(vtx1==null||vtx2==null||!vtx1.nbrs.containsKey(vname2)){
return false;
}
return true;
}
public void addedge(int vname1,int vname2,int cost){
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if(vtx1==null||vtx2==null||vtx1.nbrs.containsKey(vname2)){
return;
}
vtx1.nbrs.put(vname2,cost);
vtx2.nbrs.put(vname1,cost);
}
public void removeedge(int vname1,int vname2){
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if(vtx1==null||vtx2==null||!vtx1.nbrs.containsKey(vname2)){
return;
}
vtx1.nbrs.remove(vname2);
vtx2.nbrs.remove(vname1);
}
public void display(){
ArrayList keys = new ArrayList<>(vtces.keySet());
for(int key : keys){
Vertex vtx = vtces.get(key);
System.out.println(key + " : “+ vtx.nbrs);
}
}
private class DijkstraPair implements Comparable{
int vname;
String psf;
int cost;
public int compareTo(DijkstraPair o){
return o.cost-this.cost;
}
}
public HashMap<Integer,Integer> dijkstra(int src){
HashMap<Integer,Integer> ans = new HashMap<>();
HashMap<Integer,DijkstraPair> map = new HashMap<>();
Heap heap = new Heap<>();
for(int key : vtces.keySet()){
DijkstraPair np = new DijkstraPair();
np.vname=key;
np.psf=””;
np.cost=Integer.MAX_VALUE;
if(key==src){
np.cost=0;
np.psf="" +key;
}
heap.add(np);
map.put(key,np);
}
while(!heap.isEmpty()){
DijkstraPair rp = heap.remove();
map.remove(rp.vname);
ans.put(rp.vname,rp.cost);
for(int nbr : vtces.get(rp.vname).nbrs.keySet()){
if(map.containsKey(nbr)){
int oc = map.get(nbr).cost;
int nc = rp.cost+vtces.get(rp.vname).nbrs.get(nbr);
if(nc<oc){
DijkstraPair gp = map.get(nbr);
gp.psf=rp.psf+nbr;
gp.cost=nc;
heap.updatePriority(gp);
}
}
}
}
return ans;
}
}
class Heap<T extends Comparable>{
ArrayList data = new ArrayList<>();
HashMap<T,Integer> map = new HashMap<>();
public void add(T item){
data.add(item);
map.put(item,data.size()-1);
upheapify(data.size()-1);
}
private void upheapify(int ci){
int pi=(ci-1)/2;
if(isLarger(data.get(ci),data.get(pi))>0){
swap(pi,ci);
upheapify(pi);
}
}
private void swap(int i,int j){
T ith = data.get(i);
T jth = data.get(j);
data.set(i,jth);
data.set(j,ith);
map.put(ith,j);
map.put(jth,i);
}
public void display(){
System.out.println(data);
}
public int size(){
return this.data.size();
}
public boolean isEmpty(){
return this.data.size()==0;
}
public T remove(){
swap(0,this.data.size()-1);
T rv=this.data.remove(this.data.size()-1);
downheapify(0);
map.remove(rv);
return rv;
}
public void downheapify(int pi){
int lci=2pi+1;
int rci=2pi+2;
int mini=pi;
if(lci<this.data.size()&&isLarger(data.get(lci),data.get(mini))>0){
mini=lci;
}
if(rci<this.data.size()&&isLarger(data.get(rci),data.get(mini))>0){
mini=rci;
}
if(mini!=pi){
swap(mini,pi);
downheapify(mini);
}
}
public T get(){
return this.data.get(0);
}
public int isLarger(T t,T o){
return t.compareTo(o);
}
public void updatePriority(T pair){
int index=map.get(pair);
upheapify(index);
}
}
Dijkstra Algorithm challenge
@sanchit02,
Maintain 2 arrays distance and visited (boolean) of size n + 1. Put all values in distance as Integer.Max_Value. After that put distance[src] as 0. Now make a priority queue. To the heap add a node src and cost = 0.
Start a while loop until the heap is empty. Get the first node in heap. Now if its already visited continue. Else get neighbours of current node. Update value only if not visited and new val < old val. Insert node in the heap (duplicated can be present).
You can also test your code for the test below:
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 36 53 91 35 88 27 30 43 54 74 41
Your output: 20 53 40 68 86 68 57 85 47 53 106 44 123 42 59 78 54 109 56
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.