数据结构第二季 Day11 图 Kruskal算法、Dijkst

一、最短路径基础知识

1、最短路径的定义是什么？

• 最短路径(Shortest Path)：两顶点之间权值之和最小的路径(有向图、无向图均适用，不能有负权环)

image.png

2、最短路径适用于无权图吗？

• 适合：无权图相当于是全部边权值为 1 的有权图

image.png

3、如果有负权边，存在最短路径吗？

• 有负权边，但是没有负权环时，存在最短路径

image.png

4、为什么有负权环时不存在最短路径？

• 经过负权环，路径可以无限短

image.png

5、最短路径的常见算法有哪些？（单源、多源）

image.png

二、Dijkstra 算法

1、Dijkstra 算法是计算单源还是多源？什么情况不能使用？

• Dijkstra 属于单源最短路径算法，用于计算一个顶点到其他所有顶点的最短路径
• 使用前提：不能有负权边

image.png

2、Dijkstra 算法的等价思考，非常有助于帮助理解算法的核心思想？

• 核心结论(关键信息)：
• 后离开桌面的小石头 都是被 先离开桌面的小石头 拉起来的

image.png 核心结论

3、Dijkstra - 执行过程？

image.png image.png image.png

4、什么叫做松弛操作？（感觉这个取名字的思路不错）

• 松弛操作的意思：尝试找出更短的路径

  
  image.png

5、思考：遍历 map 时，希望获取 value 值最小的那个 key 怎么办？

• 最直接的思路

    private Entry<Vertex<V, E>, E> getMinPath(Map<Vertex<V, E>, E> relaxVertices) {
        Entry<Vertex<V, E>, E> minEntry = null;
        for (Entry<Vertex<V, E>, E> entry : relaxVertices.entrySet()) {
            if (minEntry == null) {
                minEntry = entry;
            } else if (weightManager.compare(minEntry.getValue(), entry.getValue()) > 0) {
                minEntry = entry;
            }
        }
        return minEntry;
    }

• 进化版本一：合并 if else

    private Entry<Vertex<V, E>, E> getMinPath(Map<Vertex<V, E>, E> relaxVertices) {
        Entry<Vertex<V, E>, E> minEntry = null;
        for (Entry<Vertex<V, E>, E> entry : relaxVertices.entrySet()) {
            if (minEntry == null || weightManager.compare(minEntry.getValue(), entry.getValue()) > 0) {
                minEntry = entry;
            }
        }
        return minEntry;
    }

• 进化版本二：使用迭代器

    private Entry<Vertex<V, E>, E> getMinPath(Map<Vertex<V, E>, E> relaxVertices) {
        Iterator<Entry<Vertex<V, E>, E>> iterator = relaxVertices.entrySet().iterator();
        if (!iterator.hasNext()) return null;
        Entry<Vertex<V, E>, E> minEntry = iterator.next();
        while (iterator.hasNext()) {
            Entry<Vertex<V, E>, E> entry = iterator.next();
            if (weightManager.compare(minEntry.getValue(), entry.getValue()) > 0) {
                minEntry = entry;
            }
        }
        return minEntry;
    }

6、Dijkstra 代码实现

    private Map<V, PathInfo<V, E>> dijkstra(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;
        
        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
        paths.put(beginVertex, new PathInfo<>(weightManager.zero()));

        while (!paths.isEmpty()) {
            Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPath(paths);
            // minVertex离开桌面
            Vertex<V, E> minVertex = minEntry.getKey();
            PathInfo<V, E> minPath = minEntry.getValue();
            selectedPaths.put(minVertex.value, minPath);
            paths.remove(minVertex);
            // 对它的minVertex的outEdges进行松弛操作
            for (Edge<V, E> edge : minVertex.outEdges) {
                // 如果edge.to已经离开桌面，就没必要进行松弛操作
                if (selectedPaths.containsKey(edge.to.value)) continue;
                relaxForDijkstra(edge, minPath, paths);
            }
        }
        
        selectedPaths.remove(begin);
        return selectedPaths;
    }
    
    /**
     * 松弛
     * @param edge 需要进行松弛的边
     * @param fromPath edge的from的最短路径信息
     * @param paths 存放着其他点（对于dijkstra来说，就是还没有离开桌面的点）的最短路径信息
     */
    private void relaxForDijkstra(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<Vertex<V, E>, PathInfo<V, E>> paths) {
        // 新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);
        // 以前的最短路径：beginVertex到edge.to的最短路径
        PathInfo<V, E> oldPath = paths.get(edge.to);
        if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return;
        
        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to, oldPath);
        } else {
            oldPath.edgeInfos.clear();
        }

        oldPath.weight = newWeight;
        oldPath.edgeInfos.addAll(fromPath.edgeInfos);
        oldPath.edgeInfos.add(edge.info());
    }