dijkstra

参考链接：

• https://www.baeldung.com/java-dijkstra
• https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-in-java-using-priorityqueue/

image.png

小顶堆实现，查找unsettled中距离源点最小的节点时间复杂度较低，但是小顶堆里，一个节点可能同时存在不止一个。

import java.util.*;

public class Dijkstra {

    public static void main(String[] args) {
        Node nodeA = new Node("A");
        Node nodeB = new Node("B");
        Node nodeC = new Node("C");
        Node nodeD = new Node("D");
        Node nodeE = new Node("E");
        Node nodeF = new Node("F");
        nodeA.distToSource = 0;
        nodeA.adjacent.put(nodeB,10);
        nodeA.adjacent.put(nodeC,15);
        nodeB.adjacent.put(nodeD,12);
        nodeB.adjacent.put(nodeF,15);
        nodeC.adjacent.put(nodeE,10);
        nodeD.adjacent.put(nodeE,2);
        nodeD.adjacent.put(nodeF,1);
        nodeF.adjacent.put(nodeE,5);
        List<Node> nodes = new ArrayList<>(Arrays.asList(nodeA,nodeB,nodeC,nodeD,nodeE,nodeF));
        Dijkstra obj = new Dijkstra();
        int minDist = obj.dijkstra(nodes, nodeA, nodeE);

    }

    public int dijkstra(List<Node> nodes, Node source, Node destination){
        Set<Node> settled = new HashSet<>();
        PriorityQueue<Node> unSettled = new PriorityQueue<>((node1, node2) -> node1.distToSource - node2.distToSource);
        unSettled.add(source);
        while(unSettled.size()>0){
            Node node = unSettled.poll();
            if(settled.contains(node)){// 因为小顶堆里，一个节点可能同时存在不止一个
                continue;
            }
            node.shortestPath = new ArrayList<>(node.shortestPath);
            node.shortestPath.add(node.name);
            settled.add(node);
            if(node == destination){
                return destination.distToSource;
            }
            for (Map.Entry<Node, Integer> entry : node.adjacent.entrySet()) {
                Node adjacent = entry.getKey();
                int edgeDist = entry.getValue();
                if(!settled.contains(adjacent)){
                    if(node.distToSource+edgeDist < adjacent.distToSource){
                        adjacent.distToSource = node.distToSource+edgeDist;
                        adjacent.shortestPath = new ArrayList<>(node.shortestPath);
                    }
                    unSettled.offer(adjacent);
                }
            }
        }
        return destination.distToSource;
    }

    static class Node{
        String name = null;
        int distToSource = Integer.MAX_VALUE;
        Map<Node, Integer> adjacent = new HashMap<>();
        List<String> shortestPath = new LinkedList<>();

        public Node(String name){
            this.name = name;
        }
    }
}