ShortestPath294.java

/* File:    ShortestPath294.java
 * Created: 2019-05-08
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2019 Hogwart Inc.
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

//=================================================================================================

public class ShortestPath294 {

    public static void main(String[] args) {
        Map<Integer, Integer> elevations = new HashMap<>();
        elevations.put(0, 5);
        elevations.put(1, 25);
        elevations.put(2, 15);
        elevations.put(3, 20);
        elevations.put(4, 10);
        
        int[][] weights = {
            {0, 1, 10},
            {0, 2, 8},
            {0, 3, 15},
            {1, 3, 12},
            {2, 4, 10},
            {3, 4, 5},
            {3, 0, 17},
            {4, 0, 10},
            {4, 2, 1}
        };

        findPath(elevations, weights);

        elevations.clear();
        elevations.put(0, 5);
        elevations.put(1, 15);
        elevations.put(2, 10);
        elevations.put(3, 25);
        elevations.put(4, 10);
        elevations.put(5, 20);
        elevations.put(6, 0);

        int[][] weights2 = {
            {0, 1, 3},
            {0, 2, 1},
            {1, 5, 5},
            {2, 4, 1},
            {2, 6, 1},
            {4, 0, 0},
            {4, 5, 1},
            {5, 0, 5},
            {5, 4, 1},
            {6, 0, 2},
        };

        findPath(elevations, weights2);
    } // main

    /**
     * Finds smallest weight path that ascends and then descends
     * @param elevations
     * @param weights
     */
    public static void findPath(Map<Integer, Integer> elevations, int[][] weights) {
        Map<String, Integer> pathsWeight = new HashMap<>();
        Map<Integer, List<Integer>> neighbors = new HashMap<>();
        for(int[] path : weights) {
            pathsWeight.put(path[0] + "-" + path[1], path[2]);
            if(!neighbors.containsKey(path[0])) {
                neighbors.put(path[0], new ArrayList<>());
            }
            neighbors.get(path[0]).add(path[1]);
        }

        List<Integer> bestPath = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        currentPath.add(0);
        int bestWeight = findPathHelper(elevations, pathsWeight, neighbors, new HashSet<Integer>(), false, 0, currentPath, 0, bestPath, Integer.MAX_VALUE);

        System.out.println(bestWeight);
        System.out.println(bestPath);
    } // findPath

    //---------------------------------------------------------------------------------------------

    /**
     * Helper method that recursively traverses all valid paths and identifies the lightest path.
     * 
     * @param elevations node to elevation map
     * @param pathsWeight path to path weight map
     * @param neighbors node to neighbors map
     * @param visited visited nodes in a path
     * @param descending are we currently descending
     * @param current current node being explored
     * @param currentPath nodes in current path so far
     * @param currentPathSum current path sum so far
     * @param bestPath best path so far
     * @param bestWeight best weight so far
     * @return best weight along current node
     */
    public static int findPathHelper(Map<Integer, Integer> elevations, Map<String, Integer> pathsWeight, Map<Integer, List<Integer>> neighbors,
     Set<Integer> visited, boolean descending, int current, List<Integer> currentPath, int currentPathSum, List<Integer> bestPath, int bestWeight) {
        int currentBestWeight = bestWeight; // multiple path can exist from a node. So we cannot return as soon as we find a path.
        // explore current node
        for(int neighbor : neighbors.get(current)) {
            String weightKey = current + "-" + neighbor;
            if(neighbor == 0) { // we are back to source i.e Destination
                if(elevations.get(neighbor) < elevations.get(current)) { // path should descend at end
                    if(currentPathSum + pathsWeight.get(weightKey) < currentBestWeight) { // is the path best path than already found?
                        bestPath.clear();
                        bestPath.addAll(currentPath);
                        bestPath.add(neighbor);
                        currentBestWeight = currentPathSum + pathsWeight.get(weightKey);
                    }
                }
            } else {
                boolean isPathValid = elevations.get(neighbor) != elevations.get(current); // Path should ascend or descend
                
                boolean expectDescend = elevations.get(neighbor) < elevations.get(current);
                isPathValid = isPathValid && (!descending || descending && expectDescend); // If we are ascending next can be either ascend or descend.
                                                                                           // But if we are descending, it must not ascend again.
                if (isPathValid) {
                    visited.add(neighbor);
                    currentPath.add(neighbor);
                    currentBestWeight = findPathHelper(elevations, pathsWeight, neighbors, visited, expectDescend, neighbor, currentPath, currentPathSum + pathsWeight.get(weightKey), bestPath, currentBestWeight);
                    currentPath.remove(currentPath.size() - 1);
                    visited.remove(neighbor);
                } else {
                    // Path is not valid. IGNORE
                }
            }
        }
        return currentBestWeight;
    } // findPathHelper

} // ShortestPath294