Dijkstra 算法说明与实现

作者:Grey

原文地址:

博客园:Dijkstra 算法说明与实现

CSDN:Dijkstra 算法说明与实现

问题描述

问题:给定出发点,出发点到所有点的距离之和最小是多少?

注:Dijkstra 算法必须指定一个源点,每个边的权值均为非负数,求这个点到其他所有点的最短距离,到不了则为正无穷, 不能有累加和为负数的环。

题目链接见:LeetCode 743. Network Delay Time

主要思路

  1. 生成一个源点到各个点的最小距离表,一开始只有一条记录,即原点到自己的最小距离为0, 源点到其他所有点的最小距离都为正无穷大

  2. 从距离表中拿出没拿过记录里的最小记录,通过这个点发出的边,更新源 点到各个点的最小距离表,不断重复这一步

  3. 源点到所有的点记录如果都被拿过一遍,过程停止,最小距离表得到了。

关键优化:加强堆结构说明

完整代码见:

class Solution {
    public static int networkDelayTime(int[][] times, int N, int K) {
        Graph graph = generate(times);
        Node from = null;
        for (Node n : graph.nodes.values()) {
            if (n.value == K) {
                from = n;
            }
        }
        HashMap<Node, Integer> map = dijkstra2(from, N);
        int sum = -1;

        for (Map.Entry<Node, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 0) {
                N--;
                continue;
            }
            N--;
            if (entry.getValue() == Integer.MAX_VALUE) {
                return -1;
            } else {
                sum = Math.max(entry.getValue(), sum);
            }
        }
        // 防止出现环的形状
        //   int[][] times = new int[][]{{1, 2, 1}, {2, 3, 2}, {1, 3, 1}};
        //        int N = 3;
        //        int K = 2;
        if (N != 0) {
            return -1;
        }
        return sum;
    }

    public static Graph generate(int[][] times) {
        Graph graph = new Graph();
        for (int[] time : times) {
            int from = time[0];
            int to = time[1];
            int weight = time[2];
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge fromToEdge = new Edge(weight, fromNode, toNode);
            //Edge toFromEdge = new Edge(weight, toNode, fromNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            //fromNode.in++;
            //toNode.out++;
            toNode.in++;
            fromNode.edges.add(fromToEdge);
            //toNode.edges.add(toFromEdge);
            graph.edges.add(fromToEdge);
            //graph.edges.add(toFromEdge);
        }

        return graph;
    }

    public static class Graph {
        public HashMap<Integer, Node> nodes;
        public HashSet<Edge> edges;

        public Graph() {
            nodes = new HashMap<>();
            edges = new HashSet<>();
        }
    }

    public static class Edge {
        public int weight;
        public Node from;
        public Node to;

        public Edge(int weight, Node from, Node to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }
    }

    public static class Node {
        public int value;
        public int in;
        public int out;
        public ArrayList<Node> nexts;
        public ArrayList<Edge> edges;

        public Node(int value) {
            this.value = value;
            in = 0;
            out = 0;
            nexts = new ArrayList<>();
            edges = new ArrayList<>();
        }
    }

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

    public static class NodeRecord {
        public Node node;
        public int distance;

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

    public static class NodeHeap {
        private Node[] nodes; // 实际的堆结构
        // key 某一个node, value 上面堆中的位置
        private HashMap<Node, Integer> heapIndexMap;
        // key 某一个节点, value 从源节点出发到该节点的目前最小距离
        private HashMap<Node, Integer> distanceMap;
        private int size; // 堆上有多少个点

        public NodeHeap(int size) {
            nodes = new Node[size];
            heapIndexMap = new HashMap<>();
            distanceMap = new HashMap<>();
            size = 0;
        }

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

        // 有一个点叫node,现在发现了一个从源节点出发到达node的距离为distance
        // 判断要不要更新,如果需要的话,就更新
        public void addOrUpdateOrIgnore(Node node, int distance) {
            if (inHeap(node)) {
                distanceMap.put(node, Math.min(distanceMap.get(node), distance));
                insertHeapify(node, heapIndexMap.get(node));
            }
            if (!isEntered(node)) {
                nodes[size] = node;
                heapIndexMap.put(node, size);
                distanceMap.put(node, distance);
                insertHeapify(node, size++);
            }
        }

        public NodeRecord pop() {
            NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
            swap(0, size - 1);
            heapIndexMap.put(nodes[size - 1], -1);
            distanceMap.remove(nodes[size - 1]);
            // free C++同学还要把原本堆顶节点析构,对java同学不必
            nodes[size - 1] = null;
            heapify(0, --size);
            return nodeRecord;
        }

        private void insertHeapify(Node node, int index) {
            while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void heapify(int index, int size) {
            int left = index * 2 + 1;
            while (left < size) {
                int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left]) ? left + 1 : left;
                smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
                if (smallest == index) {
                    break;
                }
                swap(smallest, index);
                index = smallest;
                left = index * 2 + 1;
            }
        }

        private boolean isEntered(Node node) {
            return heapIndexMap.containsKey(node);
        }

        private boolean inHeap(Node node) {
            return isEntered(node) && heapIndexMap.get(node) != -1;
        }

        private void swap(int index1, int index2) {
            heapIndexMap.put(nodes[index1], index2);
            heapIndexMap.put(nodes[index2], index1);
            Node tmp = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tmp;
        }
    }

    // 改进后的dijkstra算法
    // 从head出发,所有head能到达的节点,生成到达每个节点的最小路径记录并返回
    public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
        NodeHeap nodeHeap = new NodeHeap(size);
        nodeHeap.addOrUpdateOrIgnore(head, 0);
        HashMap<Node, Integer> result = new HashMap<>();
        while (!nodeHeap.isEmpty()) {
            NodeRecord record = nodeHeap.pop();
            Node cur = record.node;
            int distance = record.distance;
            for (Edge edge : cur.edges) {
                nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
            }
            result.put(cur, distance);
        }
        return result;
    }
}

代码说明:本题未采用题目给的二维数组的图结构,而是把二维数组转换成自己熟悉的图结构,再进行dijkstra算法。

更多

算法和数据结构笔记

参考资料

算法和数据结构体系班-左程云

12-10 18:12