CSC 364 Round Trip Planner

Files Provided

• Edge.java
• Graph.java
• UnweightedGraph.java
• WeightedEdge.java
• WeightedGraph.java
• RoundTripPlanner.java (to be modified)
• TripTester.java (required for testing)

Problem Description

Graph Diagram: see image.

We use graphs to solve a lot of real-life problems. In this case, we will apply graphs to develop a solution for a travel agent's trip planner.

The travel agent performs the following actions for above flight connection graph:

• Asks the client for their starting city and destination city
• The client then plans a round trip, which begins from the given start city and ends in the same city, with transit cities, if there are no direct connections available.
• The round trip is planned as follows:
  • The planned forward trip finds the cheapest path from the starting city to the destination city, with transit cities in the forward trip, if there are no direct connections available.
  • Next, the planned return trip finds the cheapest path from the destination city to the starting city, with transit cities in the return trip, where none of the transit cities in the forward trip (if any), are common with the transit cities on the return trip.
  • If the start and destination cities are directly connected, the return trip will not be on the same directly connected path.
  • Example:

Start at A, End at B
Forward Trip: A - P - Q - R - B
Return Trip: B - S - T - U - A

• The travel agent also provides the cost for the forward trip, the return trip, and the total cost of the round trip for the client.

Implementation

You are provided with the RoundTripPlanner.java class file. You are required to update the method implementations to fulfil the desired outcome for the travel agent. The file already consists of declared class members, constructor, and methods.

• The constructor should assign all the required class variables received as parameters.
• The constructor should also invoke the generateRoundTrip() method.
• The generateRoundTrip() method performs the necessary actions and updates the remaining class variables.
• The printRoundTrip() method prints the forward trip, the return trip, the costs for the forward trip and return trip, and the total cost of the round trip (see example output).

You are expected to decide on the methods that you will use from the provided files (Edge.java, Graph.java, UnweightedGraph.java, WeightedEdge.java, WeightedGraph.java), to achieve the desired outcome.

Testing

You are provided with the TripTester.java class. The class declares the set of cities, as well as the set of connections with the flight cost. The main method runs the userPrompt() method to obtain the user input for the start and destination city indices. Next, the RoundTripPlanner instance is created, using which, the printRoundTrip() method is invoked to print out the travel itinerary. Next, the verifyRoundTrip() method ensures that the round trip generated by the planner fulfils the desired plan for the travel agent.

Hints

• The solution for the problem is actually very small. However, you need to spend some time thinking about it, and then start coding.
• Make sure that you understand the concept of weighted graphs, shortest path, and path cost, and explore the relevant methods available in the additional files.
• To be able to generate the return path, you will need to modify the graph, so that the algorithm does not consider the edges in the forward path when generating the return path. One way is to delete the edges which were taken in the forward path. Another way, which is easier, is to change the edge weights used in the forward path to Integer.MAX_VALUE.

Sample Outputs

Sample Output 1

List of Cities
[0] Seattle
[1] San Francisco
[2] Los Angeles
[3] Denver
[4] Kansas City
[5] Chicago
[6] Boston
[7] New York
[8] Atlanta
[9] Miami
[10] Dallas
[11] Houston
Select your starting city: (0 - 11): 7
Select your destination city: (0 - 11): 10
Forward trip from New York to Dallas: New York -> Atlanta -> Dallas
Return trip from Dallas to New York: Dallas -> Kansas City -> New York
Forward route cost: 1669.0
Return route cost: 1756.0
Total trip cost: 3425.0
Roundtrip planning successful!

Sample Output 2

List of Cities
[0] Seattle
[1] San Francisco
[2] Los Angeles
[3] Denver
[4] Kansas City
[5] Chicago
[6] Boston
[7] New York
[8] Atlanta
[9] Miami
[10] Dallas
[11] Houston
Select your starting city: (0 - 11): 3
Select your destination city: (0 - 11): 5
Forward trip from Denver to Chicago: Denver -> Chicago
Return trip from Chicago to Denver: Chicago -> Kansas City -> Denver
Forward route cost: 1003.0
Return route cost: 1132.0
Total trip cost: 2135.0
Roundtrip planning successful!
Be a little more adventurous! Travel further!

Starter Files

Edge.java

public class Edge {
int u;
int v;

public Edge(int u, int v) {
this.u = u;
this.v = v;
}

public boolean equals(Object o) {
return (o instanceof Edge) && u == ((Edge)o).u && v == ((Edge)o).v;
}
}

Graph.java

public interface Graph< V> {
/** Return the number of vertices in the graph */
public int getSize();

/** Return the vertices in the graph */
public java.util.List< V> getVertices();

/** Return the object for the specified vertex index */
public V getVertex(int index);

/** Return the index for the specified vertex object */
public int getIndex(V v);

/** Return the neighbors of vertex with the specified index */
public java.util.List< Integer> getNeighbors(int index);

/** Return the degree for a specified vertex */
public int getDegree(int v);

/** Print the edges */
public void printEdges();

/** Clear the graph */
public void clear();

/** Add a vertex to the graph */
public boolean addVertex(V vertex);

/** Add an edge to the graph */
public boolean addEdge(int u, int v);

/** Add an edge to the graph */
public boolean addEdge(Edge e);

/** Remove a vertex v from the graph */
public default boolean remove(V v) {
return true; // Implementation left as an exercise
}

/** Remove an edge (u, v) from the graph */
public default boolean remove(int u, int v) {
return true; // Implementation left as an exercise
}

/** Obtain a depth-first search tree */
public UnweightedGraph< V>.SearchTree dfs(int v);

/** Obtain a breadth-first search tree */
public UnweightedGraph< V>.SearchTree bfs(int v);
}

TripTester.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class TripTester {
// user inputs for the source and destination

static int startCityIndex;
static int endCityIndex;

// array of vertices
static String[] cities = {
"Seattle", // 0
"San Francisco",// 1
"Los Angeles", // 2
"Denver", // 3
"Kansas City", // 4
"Chicago", // 5
"Boston", // 6
"New York", // 7
"Atlanta", // 8
"Miami", // 9
"Dallas", // 10
"Houston"}; // 11

// array of weighted edges [source][dest][weight]
static int[][] connections = {
{0, 1, 807}, {0, 3, 1331}, {0, 5, 2097},
{1, 0, 807}, {1, 2, 381}, {1, 3, 1267},
{2, 1, 381}, {2, 3, 1015}, {2, 4, 1663}, {2, 10, 1435},
{3, 0, 1331}, {3, 1, 1267}, {3, 2, 1015}, {3, 4, 599}, {3, 5, 1003},
{4, 2, 1663}, {4, 3, 599}, {4, 5, 533}, {4, 7, 1260}, {4, 8, 864}, {4, 10, 496},
{5, 0, 2097}, {5, 3, 1003}, {5, 4, 533}, {5, 6, 983}, {5, 7, 787},
{6, 5, 983}, {6, 7, 214},
{7, 4, 1260}, {7, 5, 787}, {7, 6, 214}, {7, 8, 888},
{8, 4, 864}, {8, 7, 888}, {8, 9, 661}, {8, 10, 781}, {8, 11, 810},
{9, 8, 661}, {9, 11, 1187},
{10, 2, 1435}, {10, 4, 496}, {10, 8, 781}, {10, 11, 239},
{11, 8, 810}, {11, 9, 1187}, {11, 10, 239}};

public static void main(String[] args) {
// print out list of cities with index values
System.out.println("List of Cities");
for (int i = 0; i < cities.length; i++) {
System.out.println("[" + i + "] " + cities[i]);
}

userPrompt();
RoundTripPlanner roundTripPlanner = new RoundTripPlanner(cities, connections, startCityIndex, endCityIndex);
roundTripPlanner.printRoundTrip();
verifyRoundTrip(roundTripPlanner);
}

static void userPrompt() {
Scanner scanner = new Scanner(System.in);
boolean firstInputDone = false;
boolean secondInputDone = false;

while (!firstInputDone || !secondInputDone) {
try {
// parse user input as startCityIndex integer
if (!firstInputDone) {
System.out.print("Select your starting city: (0 - 11): ");
startCityIndex = Integer.parseInt(scanner.next());

if (startCityIndex < 0 || startCityIndex > 11) {
throw new Exception("Start city needs to be between 0 - 11");
}

firstInputDone = true;
}

// parse user input as endCityIndex integer
if (!secondInputDone) {
System.out.print("Select your destination city: (0 - 11): ");
endCityIndex = Integer.parseInt(scanner.next());

if (endCityIndex < 0 || endCityIndex > 11) {
throw new Exception("Destination city needs to be between 0 - 11");
}

secondInputDone = true;
}
} catch (NumberFormatException ex) {
System.out.println("Invalid entry. Please enter an integer between 0 - 11");
} catch (Exception ex) {
System.out.println(ex.getMessage());
}
}
scanner.close();
}

private static void verifyRoundTrip(RoundTripPlanner roundTripPlanner) {
List< String> forwardRouteCopy = new ArrayList< String>(roundTripPlanner.getForwardRoute());
List< String> returnRouteCopy = new ArrayList< String>(roundTripPlanner.getReturnRoute());

// Removing common elements; Must make size=2; source + dest
forwardRouteCopy.retainAll(roundTripPlanner.getReturnRoute());
// Deleting common elements; Must make size > 0
returnRouteCopy.removeAll(forwardRouteCopy);

if (forwardRouteCopy.size() == 2
&& returnRouteCopy.size() != 0
&& forwardRouteCopy.get(0).equals(cities[startCityIndex])
&& forwardRouteCopy.get(1).equals(cities[endCityIndex])) {
System.out.println("Roundtrip planning successful!");
if (roundTripPlanner.getForwardRoute().size() == 2
|| roundTripPlanner.getReturnRoute().size() == 2) {
System.out.println("Be a little more adventurous! Travel further!");
}
} else {
System.out.println("Roundtrip planning not successful!");
}

}

}

UnweightedGraph.java

import java.util.*;

public class UnweightedGraph< V> implements Graph< V> {

protected List< V> vertices = new ArrayList< >(); // Store vertices
protected List< List< Edge>> neighbors = new ArrayList< >(); // Adjacency lists

/**
* Construct an empty graph
*/
protected UnweightedGraph() {
}

/**
* Construct a graph from vertices and edges stored in arrays
*/
protected UnweightedGraph(V[] vertices, int[][] edges) {
for (int i = 0; i < vertices.length; i++) {
addVertex(vertices[i]);
}

createAdjacencyLists(edges, vertices.length);
}

/**
* Construct a graph from vertices and edges stored in List
*/
protected UnweightedGraph(List< V> vertices, List< Edge> edges) {
for (int i = 0; i < vertices.size(); i++) {
addVertex(vertices.get(i));
}

createAdjacencyLists(edges, vertices.size());
}

/**
* Construct a graph for integer vertices 0, 1, 2 and edge list
*/
protected UnweightedGraph(List< Edge> edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++) {
addVertex((V) (new Integer(i))); // vertices is {0, 1, ...}
}
createAdjacencyLists(edges, numberOfVertices);
}

/**
* Construct a graph from integer vertices 0, 1, and edge array
*/
protected UnweightedGraph(int[][] edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++) {
addVertex((V) (new Integer(i))); // vertices is {0, 1, ...}
}
createAdjacencyLists(edges, numberOfVertices);
}

/**
* Create adjacency lists for each vertex
*/
private void createAdjacencyLists(int[][] edges, int numberOfVertices) {
for (int i = 0; i < edges.length; i++) {
addEdge(edges[i][0], edges[i][1]);
}
}

/**
* Create adjacency lists for each vertex
*/
private void createAdjacencyLists(List< Edge> edges, int numberOfVertices) {
for (Edge edge : edges) {
addEdge(edge.u, edge.v);
}
}

@Override
/**
* Return the number of vertices in the graph
*/
public int getSize() {
return vertices.size();
}

@Override
/**
* Return the vertices in the graph
*/
public List< V> getVertices() {
return vertices;
}

@Override
/**
* Return the object for the specified vertex
*/
public V getVertex(int index) {
return vertices.get(index);
}

@Override
/**
* Return the index for the specified vertex object
*/
public int getIndex(V v) {
return vertices.indexOf(v);
}

@Override
/**
* Return the neighbors of the specified vertex
*/
public List< Integer> getNeighbors(int index) {
List< Integer> result = new ArrayList< >();
for (Edge e : neighbors.get(index)) {
result.add(e.v);
}

return result;
}

@Override
/**
* Return the degree for a specified vertex
*/
public int getDegree(int v) {
return neighbors.get(v).size();
}

@Override
/**
* Print the edges
*/
public void printEdges() {
for (int u = 0; u < neighbors.size(); u++) {
System.out.print(getVertex(u) + " (" + u + "): ");
for (Edge e : neighbors.get(u)) {
System.out.print("(" + getVertex(e.u) + ", " + getVertex(e.v) + ") ");
}
System.out.println();
}
}

@Override
/**
* Clear the graph
*/
public void clear() {
vertices.clear();
neighbors.clear();
}

@Override
/**
* Add a vertex to the graph
*/
public boolean addVertex(V vertex) {
if (!vertices.contains(vertex)) {
vertices.add(vertex);
neighbors.add(new ArrayList< Edge>());
return true;
} else {
return false;
}
}

@Override
/**
* Add an edge to the graph
*/
public boolean addEdge(Edge e) {
if (e.u < 0 || e.u > getSize() - 1) {
throw new IllegalArgumentException("No such index: " + e.u);
}

if (e.v < 0 || e.v > getSize() - 1) {
throw new IllegalArgumentException("No such index: " + e.v);
}

if (!neighbors.get(e.u).contains(e)) {
neighbors.get(e.u).add(e);
return true;
} else {
return false;
}
}

@Override
/**
* Add an edge to the graph
*/
public boolean addEdge(int u, int v) {
return addEdge(new Edge(u, v));
}

@Override
/**
* Obtain a DFS tree starting from vertex v
*/
/**
* To be discussed in Section 28.7
*/
public SearchTree dfs(int v) {
List< Integer> searchOrder = new ArrayList< >();
int[] parent = new int[vertices.size()];
for (int i = 0; i < parent.length; i++) {
parent[i] = -1; // Initialize parent[i] to -1
}
// Mark visited vertices
boolean[] isVisited = new boolean[vertices.size()];

// Recursively search
dfs(v, parent, searchOrder, isVisited);

// Return a search tree
return new SearchTree(v, parent, searchOrder);
}

/**
* Recursive method for DFS search
*/
private void dfs(int u, int[] parent, List< Integer> searchOrder, boolean[] isVisited) {
// Store the visited vertex
searchOrder.add(u);
isVisited[u] = true; // Vertex v visited

for (Edge e : neighbors.get(u)) {
if (!isVisited[e.v]) {
parent[e.v] = u; // The parent of vertex e.v is u
dfs(e.v, parent, searchOrder, isVisited); // Recursive search
}
}
}

@Override
/**
* Starting bfs search from vertex v
*/
/**
* To be discussed in Section 28.9
*/
public SearchTree bfs(int v) {
List< Integer> searchOrder = new ArrayList< >();
int[] parent = new int[vertices.size()];
for (int i = 0; i < parent.length; i++) {
parent[i] = -1; // Initialize parent[i] to -1
}
java.util.LinkedList< Integer> queue = new java.util.LinkedList< >(); // list
// used
// as
// a
// queue
boolean[] isVisited = new boolean[vertices.size()];
queue.offer(v); // Enqueue v
isVisited[v] = true; // Mark it visited

while (!queue.isEmpty()) {
int u = queue.poll(); // Dequeue to u
searchOrder.add(u); // u searched
for (Edge e : neighbors.get(u)) {
if (!isVisited[e.v]) {
queue.offer(e.v); // Enqueue w
parent[e.v] = u; // The parent of w is u
isVisited[e.v] = true; // Mark it visited
}
}
}

return new SearchTree(v, parent, searchOrder);
}

/**
* Tree inner class inside the AbstractGraph class
*/
/**
* To be discussed in Section 28.6
*/
public class SearchTree {

private int root; // The root of the tree
private int[] parent; // Store the parent of each vertex
private List< Integer> searchOrder; // Store the search order

/**
* Construct a tree with root, parent, and searchOrder
*/
public SearchTree(int root, int[] parent, List< Integer> searchOrder) {
this.root = root;
this.parent = parent;
this.searchOrder = searchOrder;
}

/**
* Return the root of the tree
*/
public int getRoot() {
return root;
}

/**
* Return the parent of vertex v
*/
public int getParent(int v) {
return parent[v];
}

/**
* Return an array representing search order
*/
public List< Integer> getSearchOrder() {
return searchOrder;
}

/**
* Return number of vertices found
*/
public int getNumberOfVerticesFound() {
return searchOrder.size();
}

/**
* Return the path of vertices from a vertex to the root
*/
public List< V> getPath(int index) {
ArrayList< V> path = new ArrayList< >();

do {
path.add(0, vertices.get(index));
index = parent[index];
} while (index != -1);

return path;
}

/**
* Print a path from the root to vertex v
*/
public void printPath(int index) {
List< V> path = getPath(index);
System.out.print("Path from " + vertices.get(root) + " to " + vertices.get(index) + ": ");
for (int i = 0; i < path.size(); i++) {
System.out.print(path.get(i));
}
System.out.println();
}

/**
* Print the whole tree
*/
public void printTree() {
System.out.println("Root is: " + vertices.get(root));
System.out.print("Edges: ");
for (int i = 0; i < parent.length; i++) {
if (parent[i] != -1) {
// Display an edge
System.out.print("(" + vertices.get(parent[i]) + ", " + vertices.get(i) + ") ");
}
}
System.out.println();
}
}
}

WeightedEdge.java

public class WeightedEdge extends Edge
implements Comparable< WeightedEdge> {

public double weight; // The weight on edge (u, v)

/**
* Create a weighted edge on (u, v)
*/
public WeightedEdge(int u, int v, double weight) {
super(u, v);
this.weight = weight;
}

/**
* Compare two edges on weights
*/
public int compareTo(WeightedEdge edge) {
if (weight > edge.weight) {
return 1;
} else if (weight == edge.weight) {
return 0;
} else {
return -1;
}
}
}

WeightedGraph.java

import java.util.*;

public class WeightedGraph< V> extends UnweightedGraph< V> {

/**
* Construct an empty
*/
public WeightedGraph() {
}

/**
* Construct a WeightedGraph from vertices and edged in arrays
*/
public WeightedGraph(V[] vertices, int[][] edges) {
createWeightedGraph(java.util.Arrays.asList(vertices), edges);
}

/**
* Construct a WeightedGraph from vertices and edges in list
*/
public WeightedGraph(int[][] edges, int numberOfVertices) {
List< V> vertices = new ArrayList< >();
for (int i = 0; i < numberOfVertices; i++) {
vertices.add((V) (new Integer(i)));
}

createWeightedGraph(vertices, edges);
}

/**
* Construct a WeightedGraph for vertices 0, 1, 2 and edge list
*/
public WeightedGraph(List< V> vertices, List< WeightedEdge> edges) {
createWeightedGraph(vertices, edges);
}

/**
* Construct a WeightedGraph from vertices 0, 1, and edge array
*/
public WeightedGraph(List< WeightedEdge> edges, int numberOfVertices) {
List< V> vertices = new ArrayList< >();
for (int i = 0; i < numberOfVertices; i++) {
vertices.add((V) (new Integer(i)));
}

createWeightedGraph(vertices, edges);
}

/**
* Create adjacency lists from edge arrays
*/
private void createWeightedGraph(List< V> vertices, int[][] edges) {
this.vertices = vertices;

for (int i = 0; i < vertices.size(); i++) {
neighbors.add(new ArrayList< Edge>()); // Create a list for vertices
}

for (int i = 0; i < edges.length; i++) {
neighbors.get(edges[i][0]).add(new WeightedEdge(edges[i][0], edges[i][1], edges[i][2]));
}
}

/**
* Create adjacency lists from edge lists
*/
private void createWeightedGraph(List< V> vertices, List< WeightedEdge> edges) {
this.vertices = vertices;

for (int i = 0; i < vertices.size(); i++) {
neighbors.add(new ArrayList< Edge>()); // Create a list for vertices
}

for (WeightedEdge edge : edges) {
neighbors.get(edge.u).add(edge); // Add an edge into the list
}
}

/**
* Return the weight on the edge (u, v)
*/
public double getWeight(int u, int v) throws Exception {
for (Edge edge : neighbors.get(u)) {
if (edge.v == v) {
return ((WeightedEdge) edge).weight;
}
}

throw new Exception("Edge does not exit");
}

/**
* Display edges with weights
*/
public void printWeightedEdges() {
for (int i = 0; i < getSize(); i++) {
System.out.print(getVertex(i) + " (" + i + "): ");
for (Edge edge : neighbors.get(i)) {
System.out.print("(" + edge.u + ", " + edge.v + ", " + ((WeightedEdge) edge).weight + ") ");
}
System.out.println();
}
}

/**
* Add edges to the weighted graph
*/
public boolean addEdge(int u, int v, double weight) {
return addEdge(new WeightedEdge(u, v, weight));
}

/**
* Get a minimum spanning tree rooted at vertex 0
*/
public MST getMinimumSpanningTree() {
return getMinimumSpanningTree(0);
}

/**
* Get a minimum spanning tree rooted at a specified vertex
*/
public MST getMinimumSpanningTree(int startingVertex) {
// cost[v] stores the cost of adding v to the tree
double[] cost = new double[getSize()];
for (int i = 0; i < cost.length; i++) {
cost[i] = Double.POSITIVE_INFINITY; // Initial cost
}
cost[startingVertex] = 0; // Cost of source is 0

int[] parent = new int[getSize()]; // Parent of a vertex
parent[startingVertex] = -1; // startingVertex is the root
double totalWeight = 0; // Total weight of the tree thus far

List< Integer> T = new ArrayList< >();

// Expand T
while (T.size() < getSize()) {
// Find smallest cost v in V - T
int u = -1; // Vertex to be determined
double currentMinCost = Double.POSITIVE_INFINITY;
for (int i = 0; i < getSize(); i++) {
if (!T.contains(i) && cost[i] < currentMinCost) {
currentMinCost = cost[i];
u = i;
}
}

if (u == -1) {
break;
} else {
T.add(u); // Add a new vertex to T
}
totalWeight += cost[u]; // Add cost[u] to the tree

// Adjust cost[v] for v that is adjacent to u and v in V - T
for (Edge e : neighbors.get(u)) {
if (!T.contains(e.v) && cost[e.v] > ((WeightedEdge) e).weight) {
cost[e.v] = ((WeightedEdge) e).weight;
parent[e.v] = u;
}
}
} // End of while

return new MST(startingVertex, parent, T, totalWeight);
}

/**
* MST is an inner class in WeightedGraph
*/
public class MST extends SearchTree {

private double totalWeight; // Total weight of all edges in the tree

public MST(int root, int[] parent, List< Integer> searchOrder, double totalWeight) {
super(root, parent, searchOrder);
this.totalWeight = totalWeight;
}

public double getTotalWeight() {
return totalWeight;
}
}

/**
* Find single source shortest paths
*/
public ShortestPathTree getShortestPath(int sourceVertex) {
// cost[v] stores the cost of the path from v to the source
double[] cost = new double[getSize()];
for (int i = 0; i < cost.length; i++) {
cost[i] = Double.POSITIVE_INFINITY; // Initial cost set to infinity
}
cost[sourceVertex] = 0; // Cost of source is 0

// parent[v] stores the previous vertex of v in the path
int[] parent = new int[getSize()];
parent[sourceVertex] = -1; // The parent of source is set to -1

// T stores the vertices whose path found so far
List< Integer> T = new ArrayList< >();

// Expand T
while (T.size() < getSize()) {
// Find smallest cost v in V - T
int u = -1; // Vertex to be determined
double currentMinCost = Double.POSITIVE_INFINITY;
for (int i = 0; i < getSize(); i++) {
if (!T.contains(i) && cost[i] < currentMinCost) {
currentMinCost = cost[i];
u = i;
}
}

if (u == -1) {
break;
} else {
T.add(u); // Add a new vertex to T
} // System.out.println("Removing " + u + " cost: " + cost[u]);

// Adjust cost[v] for v that is adjacent to u and v in V - T
for (Edge e : neighbors.get(u)) {
if (!T.contains(e.v) && cost[e.v] > cost[u] + ((WeightedEdge) e).weight) {
cost[e.v] = cost[u] + ((WeightedEdge) e).weight;
parent[e.v] = u;
}
}
} // End of while

// Create a ShortestPathTree
return new ShortestPathTree(sourceVertex, parent, T, cost);
}

/**
* ShortestPathTree is an inner class in WeightedGraph
*/
public class ShortestPathTree extends SearchTree {

private double[] cost; // cost[v] is the cost from v to source

/**
* Construct a path
*/
public ShortestPathTree(int source, int[] parent, List< Integer> searchOrder, double[] cost) {
super(source, parent, searchOrder);
this.cost = cost;
}

/**
* Return the cost for a path from the root to vertex v
*/
public double getCost(int v) {
return cost[v];
}

/**
* Print paths from all vertices to the source
*/
public void printAllPaths() {
System.out.println("All shortest paths from " + vertices.get(getRoot()) + " are:");
for (int i = 0; i < cost.length; i++) {
printPath(i); // Print a path from i to the source
System.out.println("(cost: " + cost[i] + ")"); // Path cost
}
}
}
}