Dijkstra算法（Java实现）

• 应用场景

Dijkstra算法主要用于解决单源无环图的最短路径问题，且要求边的权重不能为负值。

• 算法实现

    public static int dijkstra(String start, String end, HashMap<String,HashMap<String,Integer>> graph){
        HashMap<String,Integer> costMap = graph.get(start);
        HashMap<String,String> parentMap = new HashMap<>();
        HashSet<String> processed = new HashSet<>();
        parentMap.put(start,null);
        processed.add(start);
        while (!costMap.isEmpty()){
            String lowest = getLowestCostNode(costMap,processed);
            if(lowest.equals(end)){
                String Node = end;
                Stack<String> stack = new Stack<>();
                stack.push(Node);
                while(parentMap.get(Node) != null){
                    stack.push(parentMap.get(Node));
                    Node = parentMap.get(Node);
                }
                System.out.print(start);
                while(!stack.isEmpty())
                    System.out.print("->" + stack.pop() );
                System.out.println();
                return costMap.get(lowest);
            }
            processed.add(lowest);
            HashMap<String,Integer> map = graph.get(lowest);
            if(map != null && !map.isEmpty()){
                for(Map.Entry<String,Integer> node : map.entrySet()){
                    int cost = costMap.get(lowest) + node.getValue();
                    if(!costMap.containsKey(node.getKey()) || (costMap.containsKey(node.getKey()) && cost < costMap.get(node.getKey()))){
                        costMap.put(node.getKey(),cost);
                        parentMap.put(node.getKey(),lowest);
                    }
                }
            }
        }
        return -1;
    }

    public static String getLowestCostNode(HashMap<String,Integer> costMap,HashSet<String> processed ){
        int min = Integer.MAX_VALUE;
        String res = null;
       for(Map.Entry<String,Integer> entry : costMap.entrySet()){
           if(!processed.contains(entry.getKey()) && entry.getValue() <= min){
               min = entry.getValue();
               res = entry.getKey();
           }
       }
       return res;
    }

• 算法测试

以下面的有向无环图为例进行测试，搜索从A到F的最短路径。

测试代码如下：

public static void main(String[] args){
        HashMap<String, HashMap<String,Integer>> graph = new HashMap<>();
        HashMap<String,Integer> map = new HashMap<>();
        map.put("B",3);
        map.put("C",2);
        graph.put("A",map);

        map = new HashMap<>();
        map.put("D",5);
        map.put("E",1);
        graph.put("B",map);

        map = new HashMap<>();
        map.put("D",5);
        map.put("E",1);
        graph.put("C",map);

        map = new HashMap<>();
        map.put("F",4);
        graph.put("D",map);

        map = new HashMap<>();
        map.put("D",3);
        map.put("F",3);
        graph.put("E",map);
        System.out.println(dijkstra("A","F",graph));
        
    }

• 输出

A->C->E->F

6

由此可知，由A到F的最短路径为A->C->E->F，长度为6.