Dijkstra算法

Dijkstra算法完成的是找到某個(gè)節(jié)點(diǎn)到其他各個(gè)節(jié)點(diǎn)的最短距離返回一個(gè)距離表，規(guī)定所有路線權(quán)重都是大于0的，一開始需要給一個(gè)點(diǎn)，因?yàn)橥瓿傻木褪钦疫@個(gè)點(diǎn)到其他各個(gè)節(jié)點(diǎn)的最短距離。

算法思路：

1）從已經(jīng)解鎖的點(diǎn)中找一個(gè)開始點(diǎn)到它最近距離的點(diǎn)

2）解鎖這個(gè)點(diǎn)的所有邊，更新距離表，距離表中一開始沒有到達(dá)這個(gè)節(jié)點(diǎn)的就新增，之前有的就進(jìn)行更新。

3）每個(gè)點(diǎn)只處理一次，進(jìn)行了一次解鎖邊集和更新距離表后就將它鎖住，返回1繼續(xù)操作直到所有可達(dá)節(jié)點(diǎn)都處理一遍即可拿到最小距離表。

為什么Dijkstra算法能夠拿到最短距離呢？

我簡單說說，嚴(yán)格證明就不談，我也不會。首先，從已經(jīng)解鎖的點(diǎn)中找到可以到達(dá)的最小距離。比如下面的這個(gè)圖，從v1開始進(jìn)行算法。

1.解鎖的有v1,拿出v1,v1所能到達(dá)的點(diǎn)，{v6,v5,v3}解鎖更新距離表為{v1:0,v6:100,v5:30,v3:10}

2.從已經(jīng)解鎖的點(diǎn)集中找到可達(dá)的最短距離的點(diǎn)，那就是v3，為什么要拿最小的呢？為什么一個(gè)點(diǎn)處理完之后就可以不管了呢？

原因是如果你是從已經(jīng)解鎖的點(diǎn)中找到的最短距離的點(diǎn)，那就說明這就是開始點(diǎn)能到達(dá)它的最短距離，就像是上面第二次處理v3，v3是v1的所有直達(dá)點(diǎn)中最短的，那么就說明從其他直達(dá)點(diǎn)走再繞回v3，在邊權(quán)值大于0的前提下距離不可能比v1直達(dá)v3要短。

每次都選出一個(gè)可達(dá)的最短距離，最終將所有點(diǎn)都找出來，那么每個(gè)點(diǎn)肯定是可達(dá)最短距離的加和，這就是貪心策略。

image-20210226210336847.png

java實(shí)現(xiàn)Dijkstra算法1.0

public static HashMap<Node, Integer> dijkstra(Node begin) {
    if (begin == null) return null;
    HashMap<Node, Integer> nodeDistanceMap = new HashMap<>();
    nodeDistanceMap.put(begin, 0);
    //鎖住已經(jīng)處理過的節(jié)點(diǎn)
    HashSet<Node> selectedNode = new HashSet<>();
    //每次找到當(dāng)前距離最短的節(jié)點(diǎn)
    while (true) {
        int minDistance = Integer.MAX_VALUE;
        Node minNode = null;
        for (Map.Entry<Node, Integer> entry : nodeDistanceMap.entrySet()) {
            Integer distance = entry.getValue();
            if (!selectedNode.contains(entry.getKey()) && distance < minDistance) {
                minDistance = distance;
                minNode = entry.getKey();
            }
        }
        if (minDistance == Integer.MAX_VALUE) break;
        for (Edge next : minNode.edges) {
            if (!nodeDistanceMap.containsKey(next.to)) {
                nodeDistanceMap.put(next.to, minDistance + next.weight);
            } else {
                nodeDistanceMap.put(next.to, Math.min(nodeDistanceMap.get(next.to), minDistance + next.weight));
            }
        }
        //鎖住Node,以后不用管它了
        selectedNode.add(minNode);
    }
    return nodeDistanceMap;

改良一下代碼，不是優(yōu)化，就是將找最小到達(dá)點(diǎn)功能給抽離出來。

//將找到最小距離的節(jié)點(diǎn)給抽離出一個(gè)函數(shù)，其實(shí)是再寫一遍，不太熟練
public static HashMap<Node, Integer> dijkstra1(Node begin) {
    if (begin == null) return null;
    HashMap<Node, Integer> distanceMap = new HashMap<>();
    distanceMap.put(begin, 0);
    HashSet<Node> lockedNodes = new HashSet<>();
    Node minNode;
    while ((minNode = getMinDistanceNode(distanceMap, lockedNodes)) != null) {
        for (Edge edge : minNode.edges) {
            Integer distance = distanceMap.get(minNode);
            Node to = edge.to;
            if (!distanceMap.containsKey(to)) {
                //add
                distanceMap.put(to, distance + edge.weight);
            } else {
                //update
                distanceMap.put(to, Math.min(distance + edge.weight, distanceMap.get(to)));
            }
        }
        lockedNodes.add(minNode);//鎖住
    }
    return distanceMap;
}

public static Node getMinDistanceNode(HashMap<Node, Integer> distanceMap, HashSet<Node> lockedNodes) {
    int min = Integer.MAX_VALUE;
    Node minNode = null;
    for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
        if (!lockedNodes.contains(entry.getKey()) && entry.getValue() < min) {
            min = entry.getValue();
            minNode = entry.getKey();
        }
    }
    return minNode;
}

優(yōu)化2.0版本，這才是進(jìn)行了優(yōu)化

思考：

通過研究dijkstra算法我們可以發(fā)現(xiàn)，核心就兩點(diǎn)
1）每次都找到那個(gè)最小距離的到達(dá)點(diǎn)，
2）遍歷那個(gè)最小距離的點(diǎn)更新距離表
很明顯第二點(diǎn)是不可能優(yōu)化的，你總得看看所有的邊看看距離怎么樣然后更新距離表。
但是第一點(diǎn)找到最小距離，我們很容易會想到使用最小堆是否能夠優(yōu)化，答案是可以的。
因?yàn)樽钚《衙看芜M(jìn)行堆的調(diào)整也不過是logN,也就是說我們可以直接使用一個(gè)小根堆來存儲距離表
不過注意一點(diǎn)，因?yàn)榫嚯x表中的距離是需要進(jìn)行更新的，所以我們需要更新后保證堆正確性，這就不能使用PriorityQueue,需要我們自己實(shí)現(xiàn)resign功能，這需要維護(hù)一個(gè)indexMap需要知道哪個(gè)位置的元素發(fā)生了更新，這個(gè)更新只會變小，不會變大，所以肯定是向上進(jìn)行heapInsert

如何在堆中完成一個(gè)節(jié)點(diǎn)的鎖住功能，避免已經(jīng)處理過的節(jié)點(diǎn)再次插入堆中?

做以下約定
1）如果indexMap中沒有這個(gè)Node，那肯定還沒有，就直接加入
2）如果有，但是index為-1，則表示加入過，但是已經(jīng)彈出，直接跳過，彈出的肯定是找到最小距離了

3. 以上都不符合表示還在堆中，進(jìn)行更新操作，需要維護(hù)堆

實(shí)現(xiàn)

用來找最小到達(dá)點(diǎn)的堆

public static class Heap {
    private static class NodeRecord {
        private Node node;
        private Integer distance;

        public NodeRecord(Node node, Integer distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    private ArrayList<NodeRecord> eleMentData;//Entry<Node,distance>
    private HashMap<Node, Integer> indexMap;//這里的Integer是下標(biāo)
    private int heapSize;

    public Heap() {
        eleMentData = new ArrayList<>();
        indexMap = new HashMap<>();
    }

    public void swap(int aIdx, int bIdx) {
        //保證下標(biāo)隨著一起改
        NodeRecord aEntry = eleMentData.get(aIdx);
        NodeRecord bEntry = eleMentData.get(bIdx);
        eleMentData.set(aIdx, bEntry);
        eleMentData.set(bIdx, aEntry);
        indexMap.put(aEntry.node, bIdx);
        indexMap.put(bEntry.node, aIdx);
    }

    public void heapInsert(int index) {
        int father;
        //維護(hù)一個(gè)小根堆，如果父節(jié)點(diǎn)的distance比這個(gè)子節(jié)點(diǎn)要大的話需要交換
        while (compare(index, (father = (index - 1) / 2)) < 0) {
            swap(father, index);
        }
    }

    public void heapify(int index) {
        int leftChild;
        while ((leftChild = (index << 1) | 1) < heapSize) {
            int lowest = leftChild + 1 < heapSize && compare(leftChild + 1, leftChild) < 0 ? leftChild + 1 : leftChild;
            lowest = compare(index, lowest) < 0 ? index : lowest;
            if (index == lowest) break;
            swap(index, lowest);
            index = lowest;
        }
    }

    //比較兩個(gè)下標(biāo)處的Entry里distance大小
    private int compare(int i1, int i2) {
        return eleMentData.get(i1).distance - eleMentData.get(i2).distance;
    }

    //進(jìn)行三個(gè)情況的檢查和處理，完成操作
    public void addOrUpdateOrIgnore(Node node, int distance) {
        if (!indexMap.containsKey(node)) {//add
            eleMentData.add(heapSize, new NodeRecord(node, distance));
            //indexMap同步
            indexMap.put(node,heapSize++);
            heapInsert(heapSize - 1);
        } else if (indexMap.get(node) != -1) {//update
            Integer index = indexMap.get(node);
            eleMentData.get(index).distance = Math.min(eleMentData.get(index).distance, distance);
            heapInsert(index);//可能更新，維護(hù)一下
        }
    }

    public NodeRecord poll() {
        if (isEmpty()) throw new RuntimeException("no more ele...");
        final NodeRecord res = eleMentData.get(0);
        swap(0,--heapSize);
        eleMentData.set(heapSize,null);
        indexMap.put(res.node,-1);//-1:曾經(jīng)來過
        heapify(0);
        return res;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }
}

算法本身

public static HashMap<Node,Integer> dijkstra(Node begin){
    if(begin==null) return null;
    HashMap<Node,Integer> result = new HashMap<>();
    Heap smallRHeap = new Heap();
    smallRHeap.addOrUpdateOrIgnore(begin,0);
    while (!smallRHeap.isEmpty()){
        Heap.NodeRecord heapTop = smallRHeap.poll();
        for(Edge edge:heapTop.node.edges){
            smallRHeap.addOrUpdateOrIgnore(edge.to,edge.weight+heapTop.distance);
        }
        result.put(heapTop.node,heapTop.distance);
    }

    return result;
}

測試

用上面那個(gè)例子進(jìn)行測試

public static void main(String[] args) {
    int[][] matrix = {{10, 1, 3}, {100, 1, 6}, {30, 1, 5}, {5, 2, 3}, {50, 3, 4}, {20, 5, 4}, {10, 4, 6}, {60, 5, 6},};
    Graph graph = GraphGenerator.graphGenerator(matrix);
    HashMap<Node, Integer> result = dijkstra(graph.nodesMap.get(1));
    for (Map.Entry<Node, Integer> entry : result.entrySet()) {
        System.out.println("to Node{" + entry.getKey().value + "} distance:" + entry.getValue());
    }
}

這里的Graph是我自己熟悉的圖的表示方式，matrix是一個(gè)邊組成的二維數(shù)組，里面存的每個(gè)一維數(shù)組都是這樣的意思{weight,from,to}

Graph

public class Graph{
    private HashMap<Integer,Node> nodes;//Node.value map to Node
    private HashSet<Edge> edges;
    public Graph(){
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

Node

public class Node{
    private int in;
    private int out;
    private int value;
    private ArrayList<Node> nexts;
    private ArrayList<Edge> edges;
    public Node(){
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

Edge

public class Edge{
    private int weight;
    private int from;//from Node's value
    private int to;//to Node's value
    public Edge(int weight,int from,int to){
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}