Objectives

1. Sort items in a list with respect to a property.
2. Find the shortest paths between given nodes.
3. Develop readable and documented algorithms for business applications.

Scenario

Your team is working on an application for an online shopping company that sells different kinds of products and ships them via cargo companies. The company recently added new product groups to their portfolio, such as grocery and dairy, and began offering privilege programs to their customers, wherein they can get products delivered within a day. They are planning to hire/use their own drivers for such products and customers.

To enable this, they want your team to develop a map application that will be installed on the android mobile phones of drivers. The application should show the shortest paths from each delivery point and navigate the driver through to the delivery route. Navigation must begin from the warehouse and the route must be sorted with respect to the due delivery time, else the grocery and dairy products could perish, and the delivery of products purchased by privileged customers could be delayed.

One of your team members is working on transforming data from the streets and addresses of the map to the node and edge structures of a graph. Your ShortestDeliveryPath class will receive the data as nodes, which represent delivery points or intersection of roads, and edges, which represent the roads of the map.

The driver's route will be from the warehouse, which is always node 1, to the first delivery point (node 2), and then from there to the next delivery point, and so on (node n), until all the packages are delivered. Since the application needs to sort deliveries with respect to the due delivery time, the app needs to calculate the shortest path more than once. For this, you will be using the FloydWarshall algorithm to calculate all shortest path pairs at once. You need to modify the FloydWarshall class to store the street names and print the names of the streets on the route.

Details of deliveries will be held in Shipment class. You will be using the deliveryTimeDue variable to set the delivery time limit and the toNodevariable to set the delivery node. fromNode is always 1, representing the warehouse from where the driver begins. But in practice, the delivery person will get all packages from the warehouse before beginning work and will deliver each package sequentially. Thus, in practice fromNode will change depending on the location of the delivery person, but this variable does not need to be updated.

Best Practices

1. Get familiar with the FloydWarshall algorithm and its application in this project and add any getters and setters that you need.
2. Get familiar with the Shipment.java class and add any getters and setters that you need.
3. For easy readability, use full variable names instead of short 2-3 character abbreviation.
4. For code reusability, develop separate methods when available.

import java.util.ArrayList; import java.util.List; import java.util.Vector;

public class FloydWarshall { int[][] adjacencyMatrix; // stores shortest distance from i to j /* stores previous node (to go to j) of shortest path from i to j * stores where we to go before from i for reaching j from i */ int[][] comeFromMatrix; String[][] nameOfStreets;

public FloydWarshall(int numberOfNodes) { this.adjacencyMatrix = new int[numberOfNodes][numberOfNodes]; this.comeFromMatrix = new int[numberOfNodes][numberOfNodes]; this.nameOfStreets = new String[numberOfNodes][numberOfNodes]; //Initialize the matrix for (int i = 0; i < adjacencyMatrix.length; i++) { for (int j = 0; j < adjacencyMatrix[i].length; j++) { //if it is itself if (i == j) { this.adjacencyMatrix[i][j] = 0; this.comeFromMatrix[i][j] = i; } else { //if it is not itself this.adjacencyMatrix[i][j] = Integer.MAX_VALUE; this.comeFromMatrix[i][j] = -1; } } } }

// Write your methods here

public void addEdge(int fromNode, int toNode, int length , String streetName) { if (length < adjacencyMatrix[fromNode][toNode]) { adjacencyMatrix[fromNode][toNode] = length; comeFromMatrix[fromNode][toNode] = fromNode; nameOfStreets[fromNode][toNode] = streetName; } }

public Vector path(int fromNode, int toNode) { //define return Vector pathSqeuence = new Vector<>(); //check if there is a path if (comeFromMatrix[fromNode][toNode] == -1) return pathSqeuence; //go backwards until where we start int reachedFromNode = toNode; while (fromNode != reachedFromNode) { //add node to path pathSqeuence.add(0, reachedFromNode); //update reached from node reachedFromNode = comeFromMatrix[fromNode][reachedFromNode]; } pathSqeuence.add(0, fromNode); return pathSqeuence; }

public void run() { //for each intermediate node for (int k = 0; k < adjacencyMatrix.length; k++) { //for each from node for (int i = 0; i < adjacencyMatrix.length; i++) { //if there is no path from i to k skip if (adjacencyMatrix[i][k] >= Integer.MAX_VALUE) continue; //for each to node for (int j = 0; j < adjacencyMatrix.length; j++) { //if there is no path from k to j skip if (adjacencyMatrix[k][j] >= Integer.MAX_VALUE) continue; //if path from i to j is shorter with stopping at k then update path if (adjacencyMatrix[i][k] + adjacencyMatrix[k][j] < adjacencyMatrix[i][j]) { adjacencyMatrix[i][j] = adjacencyMatrix[i][k] + adjacencyMatrix[k][j]; comeFromMatrix[i][j] = comeFromMatrix[k][j]; } } } } } /** * @param fromNode * @param toNode * * @return */ public ArrayList printPath(int fromNode, int toNode) { return null; }

public static void main(String[] args) { /* * This main method is a stub. * It does nothing. * Feel free to write your own code to test your implementation. * In this case, we have nothing actionable in here, just this comment block, so the JVM should rapidly lose interest and move on to the rest of your code. */ } }

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

import java.util.ArrayList;

public class ShortestDeliveryPath {

/** * @param graph * @param deliveryList * * @return */ public static ArrayList getDeliveryRoute(FloydWarshall graph, ArrayList deliveryList) { return null; } }

Language Java