狄克斯特拉算法JAVA实现demo

狄克斯特拉算法用于在加权图中查找最短路径 ，仅当权重为正时算法才管用

public static void main(String[] args) {
    Map, Map, Integer>> graph = new HashMap<>();
  // 散列表初始化
  graph.put("start", new HashMap<>());
  graph.get("start").put("a", 6);
  graph.get("start").put("b", 2);
  graph.get("start").put("fin", 5);
  graph.put("a", new HashMap<>());
  graph.get("a").put("fin", 1);
  graph.put("b", new HashMap<>());
  graph.get("b").put("a", 3);
  graph.get("b").put("fin", 5);
  graph.put("fin", new HashMap<>());
  // 节点开销
  Map, Integer> costs = new HashMap<>();
  costs.put("a", 6);
  costs.put("b", 2);
  costs.put("fin", 5);
  // 父节点
  Map, String> parents = new HashMap<>();
  parents.put("a", "start");
  parents.put("b", "start");
  parents.put("fin", "start");
  // 已经处理过节点
  Set processd = new HashSet<>();
  Set, Integer>> entrySet = costs.entrySet();
  Map.Entry, Integer> maxme = getLastNode(entrySet,processd);
 while (maxme != null) {
        Map, Integer> stringIntegerMap = graph.get(maxme.getKey());
  Set keySet = stringIntegerMap.keySet();
  Map.Entry, Integer> finalMaxme = maxme;
  keySet.stream().forEach(o -> {
            Integer c = stringIntegerMap.get(o) + finalMaxme.getValue();
 if (costs.get(o) > c) {
                costs.put(o, c);
  parents.put(o, finalMaxme.getKey());
  }
        });
  processd.add(maxme.getKey());
  maxme = getLastNode(entrySet,processd);
  }
    costs.entrySet().forEach(System.out :: println);
  parents.entrySet().forEach(System.out :: println);

  String fin = parents.get("fin");
  List list = new ArrayList<>();
  list.add("fin");
 while (StringUtils.isNotEmpty(fin)) {
        list.add(fin);
  fin = parents.get(fin);
  }
    Collections.reverse(list);
  System.out.println(StringUtils.join(list, "-->"));

}

private static Map.Entry, Integer> getLastNode(Set, Integer>> entrySet, Set processd) {
    Optional, Integer>> max = entrySet.stream().filter(o -> !processd.contains(o.getKey())).min(Comparator.comparing(Map.Entry::getValue));
 if (max != null) {
        return max.orElse(null);
  }
    return null;
}