【面向对象】记一次错误的Dijkstra算法优化—动态规划与贪心

目录

• Floyd（弗洛伊德）算法
• Dijkstra（迪杰斯特拉）算法
• 联想：贪心与动态规划——不恰当的贪心导致出错

没有学过算法，请各位大佬们轻拍

本文将简单比较一下图论中最短路的两大最短路算法：Floyd（弗洛伊德）算法与Dijkstra（迪杰斯特拉）算法，并阐述一下两大算法背后的算法原理（动态规划与贪心），并记录一下由于对算法本质理解不透彻，我是怎么把自己坑了。

Floyd（弗洛伊德）算法

Floyd算法本质上是一种动态规划算法，又称“插点法”。可以形象的解释为“如果两点间的路径长度，大于这两点通通过第三点连接的路径长度，那么就修正这两点的最短路径”。

Floyd算法的Java实现如下

public class GraphAlgorithm {
    public static final int INFINITY = Integer.MAX_VALUE >> 4;
    
    public static void floyd(HashMap<Integer, HashMap<Integer, Integer>> graph) {
        for (Integer k : graph.keySet()) {
            for (Integer i : graph.keySet()) {
                if (k.equals(i)) {
                    continue;
                }
                int ik = graph.get(i).get(k);
                if (ik == INFINITY) {
                    continue;
                }
                for (Integer j : graph.keySet()) {
                    int ij = graph.get(i).get(j);
                    int kj = graph.get(k).get(j);
                    if (ik + kj < ij) {
                        graph.get(i).put(j, ik + kj);
                    }
                }
            }
        }
    }
}

非常简明的三重循环，是一个动态规划算法。

就是一个三重循环权值修正，就完成了所有顶点之间的最短路计算，时间复杂度是O(n^3)。

其实Floyd算法很好理解和实现，没什么好说的，本质就是动态规划

Dijkstra（迪杰斯特拉）算法

Dijkstra算法本质上是一种贪心算法

迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，从一个顶点到其余各顶点的最短路径算法，直到扩展到终点为止。

很难受。Dijkstra算法是一种单源最短路算法，在算法的缓存优化中，我忽略了必须是最短路为真的条件必须是“其余n-1个节点均得到最短路径”

下面是错误的堆优化并缓存的dijkstra代码，然后分析原因

public class GraphAlgorithm {
    public static final int INFINITY = Integer.MAX_VALUE >> 4;
    // 堆中保存的数据节点
    public class HeapNode implements Comparable {
        private int value;
        private int id;
        public HeapNode(int id, int value) {
            this.value = value;
            this.id = id;
        }
        public int getValue() {
            return value;
        }
        public int getId() {
            return id;
        }
        @Override
        public int compareTo(Object o) {
            return Integer.compare(value, ((HeapNode) o).getValue());
        }
    }
    // 堆优化的迪杰斯特拉算法
    public static void dijkstraWithHeap(
            HashMap<Integer, HashMap<Integer, Integer>> graph,
            int fromNodeId, int toNodeId) {
        PriorityQueue<HeapNode> sup = new PriorityQueue<>();
        HashMap<Integer, Integer> dist = new HashMap<>();
        Set<Integer> found = new HashSet<>();
        for (Integer vertex : graph.keySet()) {
            dist.put(vertex, INFINITY);
        }
        dist.put(fromNodeId, 0);
        sup.add(new HeapNode(fromNodeId, 0));
        while (!sup.isEmpty()) {
            HeapNode front = sup.poll();
            int nowShortest = front.getId();
            int minWeight = front.getValue();
            // 此处更新缓存？好像可以？我不知道
            graph.get(fromNodeId).put(nowShortest, minWeight);
            graph.get(nowShortest).put(fromNodeId, minWeight);
            if (nowShortest == toNodeId) { // 致命错误，此处不能结束函数
                return;
            }
            found.add(nowShortest);
            for (Integer ver : graph.get(nowShortest).keySet()) {
                int value = graph.get(nowShortest).get(ver);
                if (!found.contains(ver) && minWeight + value < dist.get(ver)) {
                    dist.put(ver, minWeight + value);
                    sup.add(new HeapNode(ver, minWeight + value));
                }
            }
        }
        graph.get(fromNodeId).put(toNodeId, INFINITY);
        graph.get(toNodeId).put(fromNodeId, INFINITY);
    }
}

Dijkstra是一种贪心算法，所有的最短路都只是基于已知情况做出的判断，所以在堆不为空（朴素Dijkstra是没有遍历完其余n-1个节点）之前不能结束算法，否则得到的答案可能是错误的。

此前没有发现这个问题是因为数据量不够大，只有1000余条指令，所以这样的Dijkstra算法没有出错。

当数据量增大到5000条，其中384条最短路查询指令，有13条出错。仔细排查后才发现是Dijkstra的问题。（然而这时候提交时间已经截至了，C组预定?）

而Dijkstra算法不止最短路矩阵使用了，最少换成、最少票价、最小不满意度矩阵均使用了Dijkstra算法，但这些指令没有出错。我认为原因如下：图的邻接表在数据量大的情况下，是一个稠密图，Dijkstra算法提前结束会导致缓存结果并非实际的最短路。

主要还是没有理解贪心算法的本质，导致了错误的修改。

贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，贪心算法所做出的是在某种意义上的局部最优解。

以后一定好好学习算法。不知道以后算法课会不会很难……

那么正确的缓存方式应该是这样：

public class GraphAlgorithm {
    public static final int INFINITY = Integer.MAX_VALUE >> 4;
    // 堆优化的迪杰斯特拉算法
    public static void dijkstraWithHeap(
            HashMap<Integer, HashMap<Integer, Integer>> graph,
            int fromNodeId, int toNodeId) {
        PriorityQueue<HeapNode> sup = new PriorityQueue<>();
        HashMap<Integer, Integer> dist = new HashMap<>(graph.size());
        Set<Integer> found = new HashSet<>();
        for (Integer vertex : graph.keySet()) {
            dist.put(vertex, INFINITY);
        }
        dist.put(fromNodeId, 0);
        sup.add(new HeapNode(fromNodeId, 0));
        while (!sup.isEmpty()) {
            HeapNode front = sup.poll();
            int nowShortest = front.getId();
            int minWeight = front.getValue();
            if (found.contains(nowShortest)) {
                continue;
            }
            found.add(nowShortest);
            for (Integer ver : graph.get(nowShortest).keySet()) {
                int value = graph.get(nowShortest).get(ver);
                if (!found.contains(ver) && minWeight + value < dist.get(ver)) {
                    dist.put(ver, minWeight + value);
                    sup.add(new HeapNode(ver, minWeight + value));
                }
            }
        }
        // 最后缓存数据
        for (Integer ver : dist.keySet()) {
            int minWeight = dist.get(ver);
            graph.get(fromNodeId).put(ver, minWeight);
            graph.get(ver).put(fromNodeId, minWeight);
        }
    }
}

本来可以是开心的A组，开心的满分，结果……唉?

联想：贪心与动态规划——不恰当的贪心导致出错

关于贪心和动态规划，让我想起来了一类很经典的题型，最少的钱的张数：

现在有5元、4元、3元以及1元的纸币，问7元最少要多少张纸币？

如果按照简单的贪心策略，就是7 = 5 + 1 + 1，但这显然是错的，显然7 = 4 + 3才是最优解。

如果是动态规划就不存在这个问题。

原题我记不清楚了，只记得大概坑点就是这个。当时看了题解才知道坑点是这个。

（可惜当时太菜了不懂啥事动态规划，现在也菜）

大概就这样。算法真有趣。

请大佬们多多补充，说的不对或者不好的纠正一下。

---

2019.5.16

我果然强测凉了?果然C组?