[Dijkstra] I keep getting the wrong answer

#1

Instead of getting 24 3 15 I keep getting max integer value followed by 3 and 15.
Here’s my code - https://ide.codingblocks.com/s/240421

#2

import java.util.*;

public class Main {
public static void main(String args[]) {
Graph graph = new Graph();
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t > 0){
int v = sc.nextInt();
int e = sc.nextInt();
int p=v;
int i=1;
while(p-- >0) {
graph.addVertex(Integer.toString(i));
i++;
}
while(e > 0){
String v1 = sc.next();
String v2 = sc.next();
// graph.addVertex(v1);
//graph.addVertex(v2);
int cost = sc.nextInt();
graph.addEdge(v1, v2, cost);

            e--;
        }
       // graph.display();
        String source = sc.next();
        HashMap<String, Integer> result = graph.dijkstra(source);
        ArrayList<String> entries = new ArrayList<>(result.keySet());
        for(String entry:entries){
            if(entry.equals(source)){
                continue;
            }
            System.out.print(result.get(entry) + " ");
        }
        System.out.println();
        t--;
    }
}

}

//Heap
class HeapGeneric<T extends Comparable> {
ArrayList data = new ArrayList<>();
HashMap<T, Integer> map = new HashMap<>();

public boolean isEmpty(){
    return this.data.size() == 0;
}

public void add(T item) {
	data.add(item);
	map.put(item, this.data.size()-1);
	upHeapify(data.size()-1);
}

private void upHeapify(int childIndex) {
	int parentIndex = (childIndex - 1)/2;
	
	if(isLarger(data.get(childIndex), data.get(parentIndex)) > 0) {
		swap(childIndex, parentIndex);
		upHeapify(parentIndex);
	}
}

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 T remove() {
	swap(0, this.data.size() - 1);
	T result = this.data.remove(this.data.size() - 1);
	downHeapify(0);
	
	map.remove(result);
	return result;
}

private void downHeapify(int parentIndex) {
	int leftChildIndex = 2*parentIndex + 1;
	int rightChildIndex = 2*parentIndex + 2;
	
	int minIndex  = parentIndex;
	
	if(leftChildIndex < this.data.size() && isLarger(data.get(leftChildIndex), data.get(minIndex)) > 0) {
		minIndex = leftChildIndex;
	}
	
	if(rightChildIndex < this.data.size() && isLarger(data.get(rightChildIndex), data.get(minIndex)) > 0) {
		minIndex = rightChildIndex;
	}
	
	if(minIndex != parentIndex) {
		swap(minIndex, parentIndex);
		downHeapify(minIndex);
	}
}

public int isLarger(T t, T o) {
	return t.compareTo(o);
}

public void updatePriority(T pair) {
	int index = map.get(pair);
	upHeapify(index);
}

}
//Heap

//Graph
class Graph{
private class Vertex{
HashMap<String ,Integer> neighbors = new HashMap<>();
}

HashMap<String, Vertex> vertices;

public Graph(){
	vertices = new HashMap<>();
}

public void addVertex(String vertex) {
	Vertex vtx = new Vertex();
	vertices.put(vertex, vtx);
}

public void removeVertex(String vertex) {
	Vertex vtx = vertices.get(vertex);
	ArrayList<String> keys = new ArrayList<>(vtx.neighbors.keySet());
	
	for(String key:keys) {
		Vertex neighborVtx = vertices.get(key);
		neighborVtx.neighbors.remove(vertex);
	}
	
	vertices.remove(vertex);
}

public void addEdge(String vertex1, String vertex2, int cost) {
	Vertex vtx1 = vertices.get(vertex1);
	Vertex vtx2 = vertices.get(vertex2);
	
	if(vtx1 == null || vtx2 == null || vtx1.neighbors.containsKey(vertex2)) {
		return;
	}
	
	vtx1.neighbors.put(vertex2, cost);
	vtx2.neighbors.put(vertex1, cost);
}

public void removeEdge(String vertex1, String vertex2) {
	Vertex vtx1 = vertices.get(vertex1);
	Vertex vtx2 = vertices.get(vertex2);
	
	if(vtx1 == null || vtx2 == null || !vtx1.neighbors.containsKey(vertex2)) {
		return;
	}
	
	vtx1.neighbors.remove(vertex2);
	vtx2.neighbors.remove(vertex1);
}   

public class DijkstraPair implements Comparable<DijkstraPair>{
	String vName;
	String psf;
	int cost;
	
	@Override
	public int compareTo(DijkstraPair other) {
		return other.cost - this.cost;
	}
}

public HashMap<String, Integer> dijkstra(String source) {
	HashMap<String, Integer> ans = new HashMap<>();
	HashMap<String, DijkstraPair> map = new HashMap<>();
	HeapGeneric<DijkstraPair> heap = new HeapGeneric<>();
	
	//make a pair and put in heap and map
	for(String key : vertices.keySet()) {
		DijkstraPair newPair = new DijkstraPair();
		newPair.vName = key;
		newPair.psf = "";
		newPair.cost = Integer.MAX_VALUE;
		
		//changed
		if(key.equals(source)) {
			newPair.cost = 0;
			newPair.psf = key;
		}
		
		heap.add(newPair);
		map.put(key, newPair);
	}
	
	//keep removing the pairs till the heap is empty
	while(!heap.isEmpty()) {
		//remove a pair
		DijkstraPair removedPair = heap.remove();
		map.remove(removedPair.vName);
		
		//add to ans
		ans.put(removedPair.vName, removedPair.cost);
		
		//work for nbrs which are in heap
		for(String nbr: vertices.get(removedPair.vName).neighbors.keySet()) {
			if(map.containsKey(nbr)) {
				int oldCost = map.get(nbr).cost;
				int newCost = removedPair.cost + vertices.get(removedPair.vName).neighbors.get(nbr);//changed
				
				//update the cost 
				if(newCost < oldCost) {
					DijkstraPair getPair = map.get(nbr);
					getPair.psf = removedPair.psf + nbr; //changed
					getPair.cost = newCost;
					
					heap.updatePriority(getPair);
				}
			}
		}
	}
	
	return ans;
}

}
//Graph

1 Like
#3

first of all add all vertex 1 to v

1 Like