RoutePlanner.java

import java.util.*;

/**
 * Created by Amaterasu on 7/9/17.
 */
public class RoutePlanner
{
    private static int[][] graph;
    private static boolean[] visited;
    private static int[] dist;
    private static int[] parent;
    private static List<Integer> path;
    private static int numOfCities;
    private static int source;
    private static int dest;
    private static int startFuel;
    private static int fuelTankCap;
    private static Map<String, Integer> cityMap;
    private static List<String> cities;
    
    public static void planRoute(int[][] _graph, Map<String, Integer> _cityMap,
            List<String> _cities, int _src, int _dest, int _startFuel,
                                 int _fuelTankCap) {
        graph = _graph;
        cities = _cities;
        numOfCities = cities.size();
        cityMap = _cityMap;
        source = _src;
        dest = _dest;
        startFuel = _startFuel;
        fuelTankCap = _fuelTankCap;
        path = new ArrayList<>();
        
        metaDijkstra( source, dest, startFuel );
        printSolution();
    }
    
    public static void planRoute() {
        numOfCities = cities.size();
        userInterface();
        metaDijkstra( source, dest, startFuel );
        printSolution();
    }
    
    private static int metaDijkstra(int src, int dest, int fuel) {
        
        if (dijkstra(src, dest) > fuel) {
            int min = Integer.MAX_VALUE;
            int gasStation = -1;
        
            for (int i = 0; i < numOfCities; i++) {
                int dist_to_gasStation = Integer.MAX_VALUE;
                if (cityMap.get( cities.get( i ) ) == 1) {
                    gasStation = i;
                    dist_to_gasStation = dijkstra( src, gasStation );
                }
                // Find the distance to the nearest gas station
                if (dist_to_gasStation <= fuel &&
                        dist_to_gasStation < min) {
                    System.out.println("Distance to gas station: " +
                                               dist_to_gasStation + " in " +
                                               cities.get( gasStation ));
                    min = dist_to_gasStation;
                }
            }
            if (min == Integer.MAX_VALUE) {
                System.out.println("No such path");
                return Integer.MAX_VALUE;
            }
            return metaDijkstra( gasStation, dest, fuelTankCap );
        }
        return dijkstra( src, dest );
    }
    
    // Dijkstra's shortest path algorithm. Since there is a starting point,
    // single-source shortest path is appropriate
    private static int dijkstra(int src, int dest) {
        // dist[i] holds shortest distance from src to i
        dist = new int[numOfCities];
        parent = new int[numOfCities];
        
        // visited[v] == true if vertex v is included in the shortest
        // path tree. This array holds the shortest paths to all the vertices
        visited = new boolean[numOfCities];
        
        // Initialize the arrays
        for (int v = 0; v < numOfCities; v++) {
            dist[v] = Integer.MAX_VALUE;
            parent[v] = -1;
            visited[v] = false;
        }
        
        // Distance of src vertex to itself is always 0, note the distance
        // stored is cumulative at each step
        if (src == source) {
            dist[src] = 0;
        }
    
        // Find shortest distance from u to v, (u, v)
        for (int i = 1; i < numOfCities; i++) {
            int u = minDistance( dist, visited );
            
            visited[u] = true;
            
            // If the destination vertex is reached, no need to keep walking
            // the graph and updating the shortest paths, break out of the for
            // loop
            if (u == dest) break;
            
            for (int v = 0; v < numOfCities; v++) {
                relax(u, v, graph[u][v]);
            }
        }
        return dist[dest];
    }
    
    private static void relax(int u, int v, int dist_to_v) {
        // Update dist[v] if it's not in visited and there's an
        // edge from u to v, and total weight of path from src to v
        // through u is smaller than the current value of dist[v]
        if (!visited[v] && dist_to_v != 0 &&
                dist[u] != Integer.MAX_VALUE &&
                dist[u] + dist_to_v < dist[v]) {
            dist[v] = dist[u] + dist_to_v;
            parent[v] = u;
        }
    }
    
    // Utility method for finding the vertex with the minimum distance
    // value from the set not yet visited
    private static int minDistance(int dist[], boolean
            shortestPath[]) {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;
    
        for (int v = 0; v < numOfCities; v++) {
            if (!shortestPath[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }
        return minIndex;
    }
    
    // Utility method for printing graph in matrix format
    /*private static void printMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            System.out.print("[");
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print( matrix[i][j] + ", ");
            }
            System.out.print("]\n");
        }
    }*/
    
    // Print solution
    private static void printSolution() {
//        for (int i = 0; i < numOfCities; i++) {
//            System.out.println(cities.get( i ) + ": " + dist[i]);
//        }
    
        System.out.println(path.toString());
        
        List<String> result = new ArrayList<>();
        
        // Reverse walk the parent[] array from the destination
        System.out.println("The shortest route found is:");
        System.out.println( "Parent array:" + Arrays.toString( parent ));
        int prev = dest;
        
        while (prev != -1) {
            result.add( cities.get( prev ) );
//            System.out.println(cities.get( prev ));
            prev = parent[prev];
        }
        
        // Reverse the list
        Collections.reverse( result );
        System.out.println("Result: " + result.toString());
        
        // If the path does not lead all the way back from the destination to
        // the source, there is a "break" (parent[i] == -1) somewhere in the
        // middle of the path, so there is no path
        if (!result.get( 0 ).equals( cities.get( source ) )) {
            System.out.println("printSolution: No such path.");
        }
        else {
            for (String city : result) {
                System.out.println( city );
            }
        }
    }
}