import java.util.Collections;
class edge {
char p1, p2;
int w;
edge(char p1, char p2, int w) {
this.p1 = p1;
this.p2 = p2;
this.w = w;
}
}
class sssp implements Comparable<sssp> {
char n;
int w;
sssp(char n, int d) {
this.n = n;
this.w = d;
}
public int compareTo(sssp e) {
if (this.w > e.w) {
return 1;
} else {
return -1;
}
}
}
class graph {
static final int infinity = 9999;
ArrayList<edge> edges = new ArrayList<>();
ArrayList<sssp> minimumD = new ArrayList <>();
ArrayList<sssp> currentD = new ArrayList <>();
ArrayList<sssp> helperD = new ArrayList <>();
int numberV=0;
char source;
graph(ArrayList<edge> list, char s) {
this.edges = list;
this.source = s;
currentD.add(new sssp(source, 0));
numberV++;
initialD();
doStuff();
}
void doStuff() {
sssp latestN = new sssp(source, 0);
for (int i = 0; i < numberV; i++) {
for (sssp e : currentD) {
int newW = minimum(weight(e.n), latestN.w + weight(latestN.n, e.n));
helperD.add(new sssp(e.n, newW));
}
currentD.clear();
currentD.addAll(helperD);
Collections.sort(currentD);
latestN = (currentD.get(0));
minimumD.add(latestN);
currentD.remove(0);
Collections.sort(currentD);
helperD.clear();
}
}
void initialD() {
for (edge e : edges) {
if (! exist(e.p1, currentD)) {
currentD.add(new sssp(e.p1, infinity));
numberV++;
}
if (! exist(e.p2, currentD)) {
currentD.add(new sssp(e.p2, infinity));
numberV++;
}
}
}
int minimum(int x, int y) {
if (x < y) {
return x;
}
return y;
}
int weight(char x) {
for (sssp e : currentD) {
if (e.n == x) {
return e.w;
}
}
return infinity;
}
int weight(char x, char y) {
if (x == y) {
return 0;
}
for (edge e : edges) {
if (e.p1 == x && e.p2 == y) {
return e.w;
}
}
return infinity;
}
boolean exist(char x, ArrayList<sssp> list) {
for (sssp e : list) {
if (e.n == x) {
return true;
}
}
return false;
}
void printsssp(sssp e){
System.out.println(" " + e.n + " " + e.w);
}
void printD(){
printD(minimumD);
}
void printD(ArrayList<sssp> D) {
for (sssp e : D) {
printsssp(e);
}
}
}
class work {
public static void main(String args[]) {
ArrayList<edge> list = new ArrayList<>();
list.add(new edge('A', 'B', 10));
list.add(new edge('A', 'C', 3));
list.add(new edge('B', 'D', 2));
list.add(new edge('B', 'C', 1));
list.add(new edge('C', 'D', 8));
list.add(new edge('C', 'E', 2));
list.add(new edge('D', 'E', 7));
list.add(new edge('E', 'D', 9));
list.add(new edge('C', 'B', 4));
graph obj = new graph(list, 'A');
obj.printD();
}
}
gangsta style coding 🫡
ReplyDelete