数据结构第二季 Day12 图 Bellman-Ford、Flo

一、Bellman-Ford 算法

1、Bellman-Ford 支持负权边吗？能检测出是否有负权环吗？算法核心原理是什么？

• Bellman-Ford 也属于单源最短路径算法，支持负权边，还能检测出是否有负权环
• 算法原理：对所有的边进行 V-1 次松弛操作（V 是节点数量），得到所有可能的最短路径
• 时间复杂度：O(EV)，E 是边数量，V 是节点数量

image.png image.png

2、Bellman-Ford 的算法练习实例？（动手练练）

image.png image.png image.png

3、 如何检测图是否存在负权环？

• 对所有的边进行 V-1 次松弛操作之后，再进行一次松弛操作。
• 如果第 V 次松弛操作成功，则表示有负权环
• 如果第 V 次松弛操作失败（没对结果造成影响），则表示无负权环

4、Bellman-Ford 算法实现代码

    //bellman-ford 最短路径的算法(可以有负权边)
    private Map<V, PathInfo<V, E>> bellmanFord(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;

        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        selectedPaths.put(begin, new PathInfo<>(weightManager.zero()));

        int count = vertices.size() - 1;
        for (int i = 0; i < count; i++) { // v - 1 次
            for (Edge<V, E> edge : edges) {
                PathInfo<V, E> fromPath = selectedPaths.get(edge.from.value);
                if (fromPath == null) continue;
                relax(edge, fromPath, selectedPaths);
            }
        }

        for (Edge<V, E> edge : edges) {
            PathInfo<V, E> fromPath = selectedPaths.get(edge.from.value);
            if (fromPath == null) continue;
            if (relax(edge, fromPath, selectedPaths)) {
                System.out.println("有负权环");
                return null;
            }
        }

        selectedPaths.remove(begin);
        return selectedPaths;
    }

    private boolean relax(Edge<V, E> edge, PathInfo<V, E> fromPathInfo, Map<V, PathInfo<V, E>> paths) {
        E newWeight = weightManager.add(edge.weight, fromPathInfo.weight);
        PathInfo<V, E> oldPath = paths.get(edge.to.value);
        if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return false;
        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to.value, oldPath);
        } else {
            oldPath.edgeInfos.clear();
        }

        oldPath.weight = newWeight;
        oldPath.edgeInfos.addAll(fromPathInfo.edgeInfos);
        oldPath.edgeInfos.add(edge.info());
        return true;
    }

二、Floyd 算法

1、Floyd算法的主要思想？

image.png

2、Floyd算法的代码实现？（听说使用了动态规划的思想，反正我是没太看懂，后面学完动态规划，再回来看看）

    @Override
    public Map<V, Map<V, PathInfo<V, E>>> shortestPath() {
        Map<V, Map<V, PathInfo<V, E>>> paths = new HashMap<>();
        // 初始化
        for (Edge<V, E> edge : edges) {
            Map<V, PathInfo<V, E>> map = paths.get(edge.from.value);
            if (map == null) {
                map = new HashMap<>();
                paths.put(edge.from.value, map);
            }
            
            PathInfo<V, E> pathInfo = new PathInfo<>(edge.weight);
            pathInfo.edgeInfos.add(edge.info());
            map.put(edge.to.value, pathInfo);
        }

        vertices.forEach((V v2, Vertex<V, E> vertex2) -> {
            vertices.forEach((V v1, Vertex<V, E> vertex1) -> {
                vertices.forEach((V v3, Vertex<V, E> vertex3) -> {
                    if (v1.equals(v2) || v2.equals(v3) || v1.equals(v3)) return;
                    
                    // v1 -> v2
                    PathInfo<V, E> path12 = getPathInfo(v1, v2, paths);
                    if (path12 == null) return;
                    
                    // v2 -> v3
                    PathInfo<V, E> path23 = getPathInfo(v2, v3, paths);
                    if (path23 == null) return;
                    
                    // v1 -> v3 
                    PathInfo<V, E> path13 = getPathInfo(v1, v3, paths);
                    
                    E newWeight = weightManager.add(path12.weight, path23.weight);
                    if (path13 != null && weightManager.compare(newWeight, path13.weight) >= 0) return;
                    
                    if (path13 == null) {
                        path13 = new PathInfo<V, E>();
                        paths.get(v1).put(v3, path13);
                    } else {
                        path13.edgeInfos.clear();
                    }
                    
                    path13.weight = newWeight;
                    path13.edgeInfos.addAll(path12.edgeInfos);
                    path13.edgeInfos.addAll(path23.edgeInfos);
                });
            });
        });
        
        return paths;
    }
    
    private PathInfo<V, E> getPathInfo(V from, V to, Map<V, Map<V, PathInfo<V, E>>> paths) {
        Map<V, PathInfo<V, E>> map = paths.get(from);
        return map == null ? null : map.get(to);
    }