1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
| package airbnb;
import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.PriorityQueue; import java.util.Queue;
public class ShortestPath {
public static void main(String[] args) { List<List<Integer>> relations = new LinkedList<>(); for (int i = 0; i < 9; i++) { relations.add(new LinkedList<>()); switch (i) { case 0: relations.get(i).add(1);relations.get(i).add(4);break; case 1: relations.get(i).add(2);break; case 2: relations.get(i).add(3);break; case 3: relations.get(i).add(4);break; case 4: relations.get(i).add(5);relations.get(i).add(9);break; case 5: relations.get(i).add(6);break; case 6: relations.get(i).add(7);break; case 7: relations.get(i).add(8);break; case 8: relations.get(i).add(9);break; case 9: relations.get(i).add(0);break; } } ShortestPath path = new ShortestPath(); List<Node> res = path.findShortestPath(relations, 0, 9); for (Node node : res) { System.out.println(node.person); } } public List<Node> findShortestPath(List<List<Integer>> relations, int start, int target) { if (relations == null || relations.size() < 0) { return null; } HashMap<Integer, Node> map = new HashMap<>(); for (int i = 0; i < relations.size(); i++) { Node person; if (map.containsKey(i)) { person = map.get(i); } else { person = new Node(i); map.put(i, person); } if (i == start) { person.minCost = 0; person.minPath.add(person); } for (Integer integer : relations.get(i)) { Node after = map.getOrDefault(integer, new Node(integer)); map.put(integer, after); person.frontier.add(after); } } dijkstra(map, start, target); return map.get(target).minPath; } public void dijkstra(HashMap<Integer, Node> map, int start, int target) { PriorityQueue<Node> frontiers = new PriorityQueue<>((a,b) -> (a.minCost - b.minCost)); Node startNode = map.get(start); for (Node next : startNode.frontier) { next.minCost = (next.person - startNode.person) * (next.person - startNode.person); next.minPath = new LinkedList<>(startNode.minPath); next.minPath.add(next); frontiers.add(next); } while (!frontiers.isEmpty()) { Node cur = frontiers.poll(); for (Node next : cur.frontier) { int oldCost = next.minCost; int cost = cur.minCost + (next.person - cur.person) * (next.person - cur.person); if (cost < next.minCost) { next.minCost = cost; next.minPath = new LinkedList<>(cur.minPath); next.minPath.add(next); } if (oldCost == Integer.MAX_VALUE) { frontiers.add(next); } } } } public class Node { int person; int minCost; List<Node> minPath; List<Node> frontier; public Node(int person) { this.person = person; minCost = Integer.MAX_VALUE; minPath = new LinkedList<>(); frontier = new LinkedList<>(); } }
}
|