(JAVA PLS)Using the principles from a circular doubly linked list, solve Dijkstr

Question

(JAVA PLS)Using the principles from a circular doubly linked list, solve Dijkstra's algorithm for the longest and shortest paths from A to N in the diagram above. In this example the Node will have multiple data objects (name, path speeds) and a previous and next node object. Note that some nodes will have more than two paths. That next or previous path will depend on the path speed. Write an algorithm that will build the algorithm as a class then solve the puzzle. Extra credit for any one who also randomizes the paths speeds (0<ps>6).  

Explanation / Answer

import java.util.*;

public class Graph{

Map<String,Integer> mymap;

int vertices;

Integer[][] costs;

String[] nodes;

Integer[] path;

Integer[] parents;

Graph(){

mymap = new HashMap<String,Integer>();

nodes = new String[100];

path = new Integer[100];

parents = new Integer[100];

vertices = 0;

costs = new Integer[100][100];

for(int i=0;i<100;i++){

for(int j=0;j<100;j++){

costs[i][j]=0;

}

}

}

public void insertedge(String src,String dst, int t){

int a,b;

if(!mymap.containsKey(src)){vertices++;mymap.put(src,vertices); nodes[vertices] = src;}

if(!mymap.containsKey(dst)){vertices++;mymap.put(dst,vertices); nodes[vertices] = dst;}

a = mymap.get(src);b = mymap.get(dst);

costs[a][b] = t;

}

public void shortestpath(String src){

int source = mymap.get(src),visits = 0,last;

for(int i=0;i<100;i++){

path[i] = 20000;

}

Boolean[] visit = new Boolean[vertices+1];

for(int i=0;i<=vertices;i++){

visit[i] = false;

}

path[source] = 0;visit[source] = true;last = source; parents[source] = source;

while(visits!=vertices){

visits++;

int min = 2000;

for(int i=1;i<=vertices;i++){

if(costs[i][last]>0){

if(path[last] + costs[i][last]<path[i]){

path[i] = path[last] + costs[i][last];

parents[i] = last;

}

}

}

for(int i=1;i<=vertices;i++){

if(!visit[i]){

if(path[i]<min){

min = path[i]; last = i;

}

}

}

visit[last] = true;

}

}

public static void main(String[] args) {

Graph graph = new Graph();

graph.insertedge("A","B",2);

graph.insertedge("B","D",2);

graph.insertedge("D","B",2);

graph.insertedge("D","H",6);

graph.insertedge("H","D",6);

graph.insertedge("L","H",3);

graph.insertedge("N","L",4);

graph.insertedge("L","N",4);

graph.insertedge("N","M",2);

graph.insertedge("K","M",3);

graph.insertedge("M","K",3);

graph.insertedge("E","K",4);

graph.insertedge("C","E",2);

graph.insertedge("E","C",2);

graph.insertedge("C","A",4);

graph.insertedge("D","G",3);

graph.insertedge("H","I",2);

graph.insertedge("J","L",5);

graph.insertedge("L","J",5);

graph.insertedge("J","M",3);

graph.insertedge("M","J",3);

graph.insertedge("F","E",4);

graph.insertedge("C","F",2);

graph.insertedge("F","C",2);

graph.insertedge("G","I",3);

graph.insertedge("I","G",3);

graph.insertedge("F","G",6);

graph.insertedge("G","F",6);

graph.insertedge("I","J",6);

graph.insertedge("J","I",6);

graph.insertedge("F","J",2);

graph.shortestpath("A");

int n = graph.mymap.get("N");

int a_to_n = graph.path[n];

System.out.println(graph.path[n]);

}

}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.