You are viewing a single comment's thread. Return to all comments →
Java8 using Trees
class Node implements Comparable<Node> { private int node; private long totalCost; private Node predecessor; public Node(int node, long totalCost) { this.node = node; this.totalCost = totalCost; } public Node(int node, long totalCost, Node predecessor) { this.node = node; this.totalCost = totalCost; this.predecessor = predecessor; } public int getNode() { return node; } public long getTotalCost() { return totalCost; } public Node getPredecessor() { return predecessor; } public void setNode(int node) { this.node = node; } public void setTotalCost(long cost) { this.totalCost = cost; } public void setPredecessor(Node predecessor) { this.predecessor = predecessor; } @Override public int compareTo(Node n) { if (totalCost == n.totalCost) { return this.node - n.node; } return (int) (this.totalCost - n.totalCost); } } class Result { public static TreeMap<Integer, TreeMap<Integer, Long>> mapNeighbors(List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight) { TreeMap<Integer, TreeMap<Integer, Long>> res = new TreeMap<>(); int n = gFrom.size(); for (int i = 0; i < n; i++) { int curNode = gFrom.get(i); int neighbor = gTo.get(i); long cost = gWeight.get(i); TreeMap<Integer, Long> map = res.get(curNode); if (map == null) { map = new TreeMap<>(); map.put(neighbor, cost); res.put(curNode, map); } else { map.put(neighbor, cost); } //2 ways traversable map = res.get(neighbor); if (map == null) { map = new TreeMap<>(); map.put(curNode, cost); res.put(neighbor, map); } else { map.put(curNode, cost); } } return res; } public static void getCost(int gNodes, List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight) { Node startNode = new Node(1, 0); TreeMap<Integer, TreeMap<Integer, Long>> neighborhood = mapNeighbors(gFrom, gTo, gWeight); TreeSet<Node> queue = new TreeSet<>(); TreeMap<Integer, Node> allNodes = new TreeMap<>(); TreeSet<Integer> checkedSet = new TreeSet<>(); queue.add(startNode); allNodes.put(1, startNode); while (!queue.isEmpty()) { Node queueNode = queue.pollFirst(); int nodeValue = queueNode.getNode(); checkedSet.add(nodeValue); if (nodeValue == gNodes) { System.out.println(queueNode.getTotalCost()); return; } long curCost = queueNode.getTotalCost(); for (Map.Entry<Integer, Long> e : neighborhood.get(nodeValue).entrySet()) { int neighborValue = e.getKey(); if (checkedSet.contains(neighborValue)) { continue; } long cost = e.getValue(); long totalCost = Math.max(curCost, cost); Node neighborNode = allNodes.get(neighborValue); if (neighborNode == null) { neighborNode = new Node(neighborValue, totalCost, queueNode); allNodes.put(neighborValue, neighborNode); queue.add(neighborNode); } else if (totalCost <= neighborNode.getTotalCost()) { queue.remove(neighborNode); neighborNode.setTotalCost(totalCost); neighborNode.setPredecessor(queueNode); queue.add(neighborNode); } } } System.out.println("NO PATH EXISTS"); } }
Seems like cookies are disabled on this browser, please enable them to open this website
Jack goes to Rapture
You are viewing a single comment's thread. Return to all comments →
Java8 using Trees