Here is the code:
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
class HeapGeneric<T extends Comparable>{
ArrayList<T> data = new ArrayList<>();
HashMap<T, Integer> map = new HashMap<>();
public void add(T item) {
data.add(item);
map.put(item, this.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;
}
private void downheapify(int pi) {
int lci = 2*pi +1;
int rci = 2*pi + 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);
}
}
class Graph {
private class Vertex{
HashMap<String, Integer> nbrs = new HashMap<>();
}
HashMap<String, Vertex> vtces;
public Graph() {
vtces = new HashMap<>();
}
public int numVertex() {
return this.vtces.size();
}
public boolean containsVertex(String vname) {
return this.vtces.containsKey(vname);
}
public void addVertex(String vname) {
Vertex vtx = new Vertex();
vtces.put(vname, vtx);
}
public int numEdges() {
int sum = 0;
ArrayList<String> keys = new ArrayList<>(vtces.keySet());
for(String key : keys) {
Vertex vtx = vtces.get(key);
sum+= vtx.nbrs.size();
}
return sum/2;
}
public boolean containsEdge(String vname1, String 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(String vname1, String 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(String vname1, String 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 removeVertex(String vname) {
Vertex vtx = vtces.get(vname);
ArrayList<String> keys = new ArrayList<>(vtx.nbrs.keySet());
for(String key : keys) {
Vertex nbrvtx = vtces.get(key);
nbrvtx.nbrs.remove(vname);
}
vtces.remove(vname);
}
public void display() {
System.out.println("-----------------------");
ArrayList<String> keys = new ArrayList<>(vtces.keySet());
for(String key : keys) {
Vertex vtx = vtces.get(key);
System.out.println(key+" : " + vtx.nbrs);
}
System.out.println("-----------------------");
}
public boolean hasPath(String vname1, String vname2, HashMap<String, Boolean> processed) {
processed.put(vname1,true);
if(containsEdge(vname1,vname2))
return true;
Vertex vtx = vtces.get(vname1);
ArrayList<String> keys = new ArrayList<>(vtx.nbrs.keySet());
for(String key : keys) {
if(!processed.containsKey(key) && hasPath(key,vname2,processed));
return true;
}
return false;
}
private class DijkstraPair implements Comparable<DijkstraPair>{
String vname;
String psf;
int cost;
@Override
public int compareTo(DijkstraPair o) {
return o.cost - this.cost;
}
}
public HashMap<String, Integer> dijkstra(String src){
HashMap<String, Integer> ans = new HashMap<>();
HashMap<String, DijkstraPair > map = new HashMap<>();
HeapGeneric<DijkstraPair> heap = new HeapGeneric<>();
for(String key : vtces.keySet()) {
DijkstraPair np = new DijkstraPair();
np.vname = key;
np.psf = "";
np.cost = Integer.MAX_VALUE;
if(key.equals(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(String 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;
}
}
public class GraphClient {
public static void main(String[] args) {
@SuppressWarnings("resource")
Scanner scn = new Scanner(System.in);
Graph graph = new Graph();
//
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addEdge("A", "B", 1);
graph.addEdge("A", "C", 2);
graph.addEdge("B", "C", 1);
graph.addEdge("D", "B", 7);
graph.addEdge("E", "B", 9);
graph.addEdge("C", "D", 1);
graph.addEdge("C", "E", 3);
graph.addEdge("D", "E", 1);
graph.display();
HashMap<String, Boolean> ulala = new HashMap<>();
if(!graph.hasPath("A", "E", ulala))
System.out.println("-1");
else
System.out.println(graph.dijkstra("A"));
// TODO Auto-generated method stub
}
}
This is the same code that mam taught in the course.
Yet the output is:
A : {B=1, C=2}
B : {A=1, C=1, D=7, E=9}
C : {A=2, B=1, D=1, E=3}
D : {B=7, C=1, E=1}
E : {B=9, C=3, D=1}
{A=0, B=-2147483645, C=-2147483646, D=-2147483648, E=2147483647}
The Graph is being printed correctly but Dijkstra is not working, please help, urgently