having 3 different costs (distance, time, money). You
can use PriorityQueue, LinkedList, ArrayList. Your
Main.java must have the following method: public static void
path(start, end, pathType)
- Finish This Java Code To Find The Path With Each Edge Having 3 Different Costs Distance Time Money You Can Use Prio 1 (186.2 KiB) Viewed 47 times
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
class Main {
public static void main(String[] args) {
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");
Node f = new Node("F");
a.addNeighbor(2, b);
a.addNeighbor(3, d);
a.addNeighbor(5, e);
b.addNeighbor(2, e);
b.addNeighbor(1, c);
b.addNeighbor(3, f);
c.addNeighbor(1, f);
d.addNeighbor(3, e);
d.addNeighbor(2, e);
dijkstra(a, f, f);
}
public static void dijkstra(Node start, Node
end, Node path) {
PriorityQueue<Node> pq
= new PriorityQueue<Node>();
start.distance = 0;
pq.add(start);
//While there are points to
explore
while(!pq.isEmpty()) {
Node
current = pq.poll(); //Remove from queue
if(current
== end) break;
for(Edge e
: current.neighbors) {
// My distance so far + the edge
int tempDistance = current.distance +
e.distance;
Node n = e.n;
// If this distance is longer than what we
found already, don't bother
if (tempDistance > n.distance)
continue;
n.distance = tempDistance;
n.prev = current;
pq.remove(n);
pq.add(n);
}
}
printPath(end);
}
public static void printPath(Node n) {
if (n == null) return;
printPath(n.prev);
System.out.println(n.name);
}
}
**************************************************************************
import java.util.ArrayList;
public class Node {
String name;
ArrayList<Edge>
neighbors;
int distance;
Node prev;
public Node(String name)
{
this.name
= name;
this.neighbors = new ArrayList<Edge>();
this.distance = Integer.MAX_VALUE;
this.prev
= null;
}
public void addNeighbor (int distance, Node n)
{
neighbors.add(new
Edge(distance, n));
n.neighbors.add(new
Edge(distance, this));
}
public int compareTo(Node other) {
return
Integer.compare(distance, other.distance);
}
}
*******************************************************************************
public class Edge {
int distance;
Node n;
public Edge(int distance, Node n){
this.distance =
distance;
this.n = n;
}
}
Museum of Natural History The Met Distance Time Money 8, 20,8 10, 30, 10 Times Square 2 2 2 1.1.1 Grand Central Station Chrysler Building 1,4, 2 1,42 1.31 Penn Station Empire State Building 75 2 3 Flatiron Building 11 1 Pace Plaza Brooklyn Bridge 35 2. 163 William Street