狄克斯特拉算法JAVA实现demo

  |   0 评论   |   60 浏览

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

    测试样例图

    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;
    }
    
    
    

    评论

    发表评论

    validate