封面画师：Nengoro(ネんごろぅ) 封面ID：66360374

本文参考视频：小马哥教育(SEEMYGO) 2019年恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化 Data Structure Visualizations

1.最短路径

1.1 基本含义

最短路径是指两个顶点之间权值之和最小的路径（有向图、无向图均使用，不能有负权环）。

对于无权图来说也有最短路径的概念，可以认为无权图相当于是全部边权值为 1 的有权图。

如果图中存在负权边，但是没有负权环的时候，这个图也有最短路径。

比如对于上图给出的存在负权边的图来说，A 到 E 的最短路径是： A – B – E

但是如果图中存在负权环，那么这个图不存在最短路径。

通过负权环， A 到 E 的路径可以无限短。

1.2 求解算法

最短路径的典型应用之一：路径规划问题。

求解最短路径的三个经典算法：

单源最短路径算法
- Dijkstra （迪杰斯特拉算法）
- Bellman-Ford （贝尔曼-福特算法）
多源最短路径算法
- Floyd（弗洛伊德算法）

2. Dijkstra

2.1 基本概念

Dijkstra 属于单源最短路径算法，用于计算一个顶点到其他所有顶点的最短路径。

使用前提：图中不能有负权边

时间复杂度： 可优化至O(ElogV) ，E 是边数量， V 是节点数量。我们待会实现的 Dijkstra 的时间复杂度并不是O(ElogV)，因为我们没有用到堆。

该算法由荷兰科学家 Edsger Wybe Dijkstra 发明，曾在 1972 年获得图灵奖， “goto有害论” 也是他提出来的。2002 年，与癌症抗争多年后，Dijkstra 去世，这一年的 PODC 奖颁给了他，获奖论文是他 1974 年关于自稳定系统的论文。为了纪念他，PODC 决定从 2003 年把这个奖项改名为 Dijkstra 奖。所以 Dijkstra 是少数获得过以自己的名字命名的奖项的人之一。

2.2 等价思考

Dijkstra 算法的原理其实跟生活中的一些自然现象完全一样。

把图上每一个顶点都想象成一块小石头，每一条边都想象成一条绳子，每一条绳子都连接着两块小石头，边的权值就是绳子的长度。将小石头和绳子平放在桌子上（下图是一张俯视图，图中黄色表示桌子）：

接下来想象一下，手拽这小石头 A ，慢慢地向上提起来，远离桌面。

那么， B、D、C、E 会依次离开桌面：

在提起小石头 A 后，桌面上的小石头会依次离开桌面，当最后一块小石头离开桌面后，一些绳子会绷直，而有些绳子会耷拉着，那么这些绷直的绳子就是 A 到其他小石头的最短路径。

依次离开的顺序取决于：小石头 A 到其他石头的最短路径。

在这一顿操作中，有一个很关键的信息： 后离开桌面的小石头，都是被先离开桌面的小石头拉起来的 。

2.3 执行过程

图中黑色顶点表示“源头”，指最先被拽起来的石头。

图中红色顶点表示直接连着被拽起来的石头的顶点，指下一步就可能被拽起来的石头。

而对于右边的表格来说，绿色表示已经“离开桌面”，已经确定了最终的最短路径；红色表示更新了最短路径信息。

步骤一：以顶点 A 为源点，求出 A 与能够直接到达的顶点之间的距离，最终确定 A 到 B 之间的最短路径；

Dijkstra执行流程1

步骤二：继续求得 A 到 D 之间的最短路径；

Dijkstra执行流程2

松弛操作（Relaxation）：更新2个顶点之间的最短路径。

这里一般是指：更新源点到另一个点的最短路径。

如何理解更新两个顶点之间最短路径的操作叫松弛操作呢？ 😕 可以把原来两个顶点之间的最短路径看成一根绳子，在没有更新最短路径前，这根绳子是绷直的，但是等到更新了新的最短路径后，新的路径相比于原来的路径更短，那么原来的绳子就会变得松弛 ，新的最短路径的 “绳子” 就会被绷直。

松弛操作的意义：尝试找出更短的路径长度，以便求出最短路径。需要注意的是，并不是每一次松弛操作都是有效的，就是说可能最先的路径就是最短的，那么后面进行的松弛操作就是无效的。

步骤三：确定 A 到 D 的最短路径后，对 DC 、 DE 边进行松弛操作，更新了 A 到 C 、 A 到 E 的最短路径，这样就求出了源点 A 到其他顶点之间的最短路径。

Dijkstra执行流程3

如果源头是 A ，要求得 A 到其他顶点的最短路径，就要对 A 的 outedges 进行松弛操作，就可以算出 A 到这些顶点可能存在的最短路径。然后从这些路径长度中找出最短的路径，这个最短的路径就是 A 到那个顶点的最短路径，这样就确认了一条最短路径。确认后，对那个顶点的 outedges 进行松弛操作，更新路径长度，又找出其中最小的，确认第二条最短路径，以此类推直到求出 A 到其他顶点的所有最短路径。

2.4 编码实现

在实现 Dijkstra 算法之前，需要先在接口Graph中添加方法，假设命名为shortestPath(V begin)，表示求得从 begin 出发到其他顶点的最短路径。

那么问题来了，返回值是什么？ 😨

对于返回值来说，最短路径长度是必要的（最短的权值之和），那么还有其他需要返回吗？ 😰

有的！如果可以，最好将最短路径连同最短路径长度一起返回出去。

我们先初步实现 Dijkstra 算法，将返回值设置为 Map ，Map 中的 key 是其他顶点的 value，Map 中的 value 就是源点到其他顶点之间最短路径长度。即： Graph接口中完整的方法是Map<V, E> shortestPath(V begin)。

1	public abstract Map<V, E> shortestPath(V begin);

初步实现

还是惯例，先说说思路：

1、获取源点（通过方法传递的参数获取），并判断是否非空

2、初始化两个 HashMap ，一个命名为selectPaths表示已经确定了的最短路径，一个命名为paths表示待确定的最短路径 “ 们 ”

3、从源点出发，初始化paths

4、重复执行以下操作，直到paths为空，paths为空时，方法返回selectPaths：

获取paths中最短的一条路径minVertex
将minVertex加入到selectPaths中，将minVertex从paths中删除
然后对minVertex的 outEdges 进行松弛操作

在上述的思路整理中，涉及到两个要点：一个是从paths中获取最短的路径，另一个是对minVertex的 outEdges 进行松弛操作。

从paths中获取最短的路径时，paths的类型是 HashMap ，我们可以采用最小堆来实现，但是使用最小堆实现有很多要点和技巧。我们选择最简单的实现方式，采用遍历方式一个个进行比较最后选出路径最小的。要对 HashMap 中的数据进行遍历，可以使用entrySet()方法，这个方法可以返回一个包含了原 Map 中数据的 Set 集合。

在获取paths中的最短路径时，由于 Set 中数据是无序的，无法直接获得第一个元素。因此我们可以设置一个临时变量，这个临时变量用来存储最短的路径，等到将所有路径都比较完后，就直接返回这个临时变量即可。

这个临时变量在最开始时会将其设置为null，在遍历 Set 时将遍历到的第一个元素赋值给这个临时变量，然后再使用这个临时变量和 Set 中其他元素进行比较，求出paths中的最短路径。为了减少临时变量的非空判断次数，我们可以使用迭代器，让这个临时变量的初始值设置成迭代器中 0 位置的元素。✌️

对minVertex的 outEdges 进行松弛操作时，就是将新的可选择的最短路径newWeight和以前的最短路径oldWeight进行比较，选出其中最短的路径。如果最短的路径是新的可选择的最短路径，就用该路径覆盖以前的最短路径，反之则不用覆盖。

新的可选择的最短路径指的是源点到minVertex的 outEdges的遍历结果 edge.from 的最短路径加上 edge.weight；以前的最短路径指的是源点到minVertex的 outEdges的遍历结果 edge.to 的最短路径。

进行松弛操作有一些注意要点，如果minVertex的 outEdges的遍历结果 edge.to 已经存入selectPaths或者 edge.to equals 源点，那么就没必要进行松弛操作。同时oldWeight为null时，可以理解为距离无穷，那么直接设置将newWeight放进paths即可。👊

那么，初步实现 Dijkstra 算法的代码如下：

@Override
public Map<V, E> shortestPath(V begin) {
    Vertex<V, E> beginVertex = vertices.get(begin);
    if (beginVertex == null) return null;

    Map<V, E> selectPaths = new HashMap<>();
    Map<Vertex<V, E>, E> paths = new HashMap<>();
    // 初始化 paths
    for (Edge<V, E> edge : beginVertex.outEdges) {
        paths.put(edge.to, edge.weight);
    }

    while (!paths.isEmpty()) {
        Map.Entry<Vertex<V, E>, E> minEntry = getMinPath(paths);
        // minEntry 离开桌面
        Vertex<V, E> minVertex = minEntry.getKey();
        selectPaths.put(minVertex.value, minEntry.getValue());
        paths.remove(minVertex);
        // 对它的 minEntry 的 outEdges 进行松弛操作
        for (Edge<V, E> edge : minVertex.outEdges) {
            // 如果 edge.to 已经离开桌面，那么就没必要进行松弛操作
            if (selectPaths.containsKey(edge.to.value) 
                /* || edge.to.equals(beginVertex)*/) continue;
            // 新的可选择的最短路径： beginVertex 到 edge.from 的最短路径 + edge.weight
            E newWeight = weightManager.add(minEntry.getValue(), edge.weight);
            // 以前的最短路径： beginVertex 到 edge.to 的最短路径
            E oldWeight = paths.get(edge.to);
            // oldWeight为null时，表示距离无穷，直接设置将newWeight放进paths即可
            if (oldWeight == null || weightManager.compare(newWeight, oldWeight) < 0){
                paths.put(edge.to, newWeight);
            }
        }
    }
    // 如果第 23 行代码不进行源点判断时
    selectPaths.remove(begin);
    return selectPaths;
}

/**
* 从 paths 中挑选一个最短的路径
* @param paths 路径集合
* @return 顶点
*/
private Map.Entry<Vertex<V, E>, E> getMinPath(Map<Vertex<V, E>, E> paths) {
    // 使用迭代器从 Set 的第一个元素开始遍历比较
    Iterator<Map.Entry<Vertex<V, E>, E>> iterator = paths.entrySet().iterator();
    Map.Entry<Vertex<V, E>, E> minEntry = iterator.next();
    while (iterator.hasNext()){
        Map.Entry<Vertex<V, E>, E> entry = iterator.next();
        if (weightManager.compare(entry.getValue(), minEntry.getValue()) < 0){
            minEntry = entry;
        }
    }
    return minEntry;
}

以上就是 Dijkstra 算法初步实现的代码，以经过初步测试，可放心 “食用”！😃

算法完善

在初步实现中，我们给其返回值设置为Map<V, E>，其中 V 表示源点到达的顶点， E 表示最短路径的权值之和。

但是我们真正想要的，并不是直接返回到达的顶点而是返回路径，当然也要返回最终到达的点和最短路径的权值之和。

因此需要更改接口Graph中的shortestPath()方法的返回值，使其返回值能够包含最短路径信息，路径信息其实就是边信息，只不过是有顺序的边信息，因此我们可以使用线性表来存储多个边信息，达到存储路径的效果。

public abstract Map<V, PathInfo<V, E>> shortestPath(V begin);

public static class PathInfo<V, E>{
    protected E weight;
    protected List<EdgeInfo<V, E>> edgeInfos = new LinkedList<>();

    public E getWeight() {
        return weight;
    }

    public void setWeight(E weight) {
        this.weight = weight;
    }

    public List<EdgeInfo<V, E>> getEdgeInfos() {
        return edgeInfos;
    }

    public void setEdgeInfos(List<EdgeInfo<V, E>> edgeInfos) {
        this.edgeInfos = edgeInfos;
    }

    @Override
    public String toString() {
        return "PathInfo{" +
            "weight=" + weight +
            ", edgeInfos=" + edgeInfos +
            '}';
    }
}

接口更改后，前往ListGraph类中更改实现的shortestPath()方法。

在修改shortestPath()时，将与返回值相关的 HashMap 的 value 类型修改为 PathInfo<V, E>。

同时getMinPath()方法的返回值类型和参数类型也要进行修改，方法内的临时变量类型也要进行修改。

为了后续方便实现 Bellman-Ford 算法，在这里将松弛操作的代码抽取出来，单独写成一个方法relaxForDijkstra()。抽取代码时，内部部分代码逻辑相比于初步实现的代码逻辑也发生了些许改变，注意理解。💢

PS：透露一下，Bellman-Ford算法中用不到这里抽取的松弛操作代码，因此将其命名为relaxForDijkstra()。

@Override
public Map<V, PathInfo<V, E>> shortestPath(V begin) {
    return dijkstra(begin);
}

public 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>> selectPaths = new HashMap<>();
    Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
    // 初始化 Paths
    for (Edge<V, E> edge : beginVertex.outEdges) {
        // 修改
        PathInfo<V, E> path = new PathInfo<>();
        path.weight = edge.weight;
        path.edgeInfos.add(edge.info());
        paths.put(edge.to, path);
    }

    while (!paths.isEmpty()) {
        Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPath(paths);
        // minEntry 离开桌面
        Vertex<V, E> minVertex = minEntry.getKey();
        PathInfo<V, E> minPath = minEntry.getValue();
        selectPaths.put(minVertex.value, minPath);
        paths.remove(minVertex);
        // 对它的 minEntry 的 outEdges 进行松弛操作
        for (Edge<V, E> edge : minVertex.outEdges) {
            // 如果 edge.to 已经离开桌面，那么就没必要进行松弛操作
            if (selectPaths.containsKey(edge.to.value)) continue;
            relaxForDijkstra(edge, minPath, paths);
        }
    }
    selectPaths.remove(begin);
    return selectPaths;
}

/**
* Dijkstra 的松弛操作
*
* @param edge     需要松弛的边
* @param fromPath edge 的 from 的最短路径信息
* @param paths    存放着其它点可能存在的最短路径信息
*/
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());
}

/**
 * 从 paths 中挑选一个最短的路径
 * @param paths 路径集合
 * @return 顶点
 */
private Map.Entry<Vertex<V, E>, PathInfo<V, E>> getMinPath(Map<Vertex<V, E>, PathInfo<V, E>> paths) {
    // 使用迭代器从 Set 的第一个元素开始遍历比较
    Iterator<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> iterator = paths.entrySet().iterator();
    Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = iterator.next();
    while (iterator.hasNext()) {
        Map.Entry<Vertex<V, E>, PathInfo<V, E>> entry = iterator.next();
        if (weightManager.compare(entry.getValue().weight, minEntry.getValue().weight) < 0) {
            minEntry = entry;
        }
    }
    return minEntry;
}

以上就是 Dijkstra 算法完善后的代码，以经过初步测试，可放心 “食用”！👏

上述代码其实还可以进行优化修改，getMinPath()方法是从 paths 中选取一条最短的路径，根据以前学过的数据结构，可以使用最小堆来实现，但这里的最小堆结构会发生变化，进而产生一些问题，有兴趣可以尝试一下。

在 Dijkstra 算法中，要求图中不能够存在负权边，注意这里是负权边。虽然在最开始时，我们说过没有负权环的图有最短路径，但是对于 Dijkstra 算法来说，负权边都不能有，更不要说负权环了。

那么问题来说，有没有一种算法也是单源最短路径算法，而且图中有负权边也能够计算呢？

那当然是有的， Bellman-Ford 就是这样的一种算法！

3. Bellman-Ford

3.1 基本概念

Bellman-Ford 也属于单源最短路径算法，支持负权边，还能够检测出是否含有负权环 。

算法原理： 对所有的边进行 V - 1 次松弛操作（V 是节点数量），得到所有可能的最短路径

时间复杂度： O(EV)， E 是边数量， V 是节点数量

下图的最好情况是恰好按从左到右的顺序对边进行松弛操作：

对所有边仅需进行 1 次松弛操作就能计算出 A 到达其他所有顶点的最短路径。

最坏情况是恰好每次都是从右到左的顺序对边进行松弛操作：

对所有边需进行 V - 1 次松弛操作才能计算出 A 到达其他所有顶点的最短路径。

最好的情况从右到左松弛操作

3.2 实际案例

假设一个图有八条边、六个顶点，然后使用 Bellman-Ford 进行松弛操作，其过程如下：

Bellman-Ford实际案例1

对上图某一条进行松弛操作时，判断能否松弛成功，就看这条边的起始顶点的最短路径是否已经确认或起始顶点是否是源点，如果已经确认或者是源点，那么就可以松弛成功，反之则不可以松弛成功。

Bellman-Ford实际案例2

Bellman-Ford实际案例3

不难分析出，经过 4 次松弛操作之后，已经计算出了 A 到其他所有顶点的最短路径。

概述一下

就是从求最短路径的图中选取所有的边，对这些边进行V - 1次松弛操作（V 指节点数量），直到确认最短路径。

当然，也有可能没有进行V -1 次就松弛操作已经求得了最短路径，但是最多进行V - 1次松弛操作一定可以求得最短路径（除非图中有负权环）。

3.3 编码实现

设置一个临时变量count，这个临时变量的值等于图中的顶点数减一。

设置一个循环，在这个循环内遍历当前图的所有边，对这些边进行松弛操作，循环次数为count次。

与 Dijkstra 相同的是，Bellman-Ford 一开始也要获取源点（通过方法传递的参数获取），并判断是否非空。但是也有不相同的地方，比如 Dijkstra 需要初始化两个 HashMap ，一个命名为selectPaths表示已经确定了的最短路径，还有一个命名为paths表示待确定的最短路径 “ 们 ”，但是对于 Bellman-Ford 来说后者并不需要，而且在 Bellman-Ford 中，selectPaths 的类型修改为Map<V, PathInfo<V, E>>。

同时，我们在进行松弛操作时，需要获取selectPaths中的边信息。在一开始时，selectPaths中没有任何边信息，获取到的边信息是空，在这里需要进行判断。如果获取到的边信息是空，直接continue即可。

但是这样又会出现一个问题，一开始时selectPaths是空的，无法获取到边信息，这个时候又直接continue了，那么就会一直无法进行松弛操作，因此我们需要在初始化selectPaths时，在这个 HashMap 中添加源点自身到自身的路径信息，最后在方法返回前删除添加的源点路径信息。添加的路径信息中不能设置边信息，因为图中自身到自身是没有边的，这只是我们假想的，但是需要添加路径权值。路径权值应该是零，这个零对于不同的类型可能不一样，比如对于整型来说，零就是0；对于双浮点数来说，零就是0.0；对于自定义类型来说，零就有可能是该类型中某个属性值为零。

这个零值应该是由用户决定的，用户使用了什么类型，这个零值就应该跟着变化，那么可以在Graph接口中的WeightManager接口添加一个方法zero()，这个方法让用户可以自行编写对象的零值，将零值的变化交给用户控制。

public interface WeightManager<E> {
    int compare(E w1, E w2);
    E add(E w1, E w2);
    // 用户自行编写的对象的零值
    E zero();  
}

有了这样的方法，我们还可以对 Dijkstra 进行修改，修改源点的初始化。在修改之前给Graph接口中的PathInfo内部类添加两个构造方法：

public static class PathInfo<V, E>{
    protected E weight;
    protected List<EdgeInfo<V, E>> edgeInfos = new LinkedList<>();

    public PathInfo() {
    }

    public PathInfo(E weight) {
        this.weight = weight;
    }
    // 省略 get/set 方法、toString() 方法
}

修改 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>> selectPaths = new HashMap<>();
    Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
    paths.put(beginVertex, new PathInfo<>(weightManager.zero()));
        // 初始化 Paths
//        for (Edge<V, E> edge : beginVertex.outEdges) {
//            PathInfo<V, E> path = new PathInfo<>();
//            path.weight = edge.weight;
//            path.edgeInfos.add(edge.info());
//            paths.put(edge.to, path);
//        }

   // 省略最短路径的选取与松弛操作 
    
    selectPaths.remove(begin);
    return selectPaths;
}

在最开始介绍 Bellman-Ford 时，这个算法可以检测出是否含有负权环 ，那么应该怎么检测呢？

Bellman-Ford 最多对每条边进行 V - 1 次松弛操作，如果图中含有负权环的话，就可以进行超过最多次的松弛操作。那么我们就可以在方法最后再进行一次松弛操作，看看这一次松弛操作能否成功进行。

那么问题又来了，怎么判断松弛操作是否成功进行呢？

我们可以将松弛操作的返回值设置成布尔类型的就可以了，成功进行了松弛操作就返回true，反之就返回false。

那么最终 Bellman-Ford 的代码如下：

@Override
public Map<V, PathInfo<V, E>> shortestPath(V begin) {
    return bellmanFord(begin);
}

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>> selectPaths = new HashMap<>();
    // 添加源点自身到自身的路径信息
    PathInfo<V, E> beginPath = new PathInfo<>();
    // 设置源点的零值
    beginPath.weight = weightManager.zero();
    // 将源点添加至selectPaths中
    selectPaths.put(begin, beginPath);

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

    for (Edge<V, E> edge : edges) {
        PathInfo<V, E> fromPath = selectPaths.get(edge.from.value);
        if (fromPath == null) continue;
        if (relax(edge, fromPath, selectPaths)) {
            System.out.println("当前图内存在负权环");
            return null;
        }
    }
	// 从selectPaths中删除源点
    selectPaths.remove(begin);
    return selectPaths;
}

/**
 * Bellman-Ford 的松弛操作
 *
 * @param edge     需要松弛的边
 * @param fromPath edge 的 from 的最短路径信息
 * @param paths    存放着其它点可能存在的最短路径信息
 */
private boolean relax(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<V, 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.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(fromPath.edgeInfos);
    oldPath.edgeInfos.add(edge.info());
    return true;
}

以上就是 Bellman-Ford 的代码，以经过初步测试，可放心 “食用”！💪

4. Floyd

4.1 概念与原理

Floyd 属于多源最短路径算法 ，能够求出任意 2 个顶点之间的最短路径，支持负权边。

要实现求出任意 2 个顶点之间的最短路径，也可以多次使用 Dijkstra 来求得最短路径。

时间复杂度： O(V³) ，效率比执行 V 次 Dijkstra 算法要好（V 是顶点数量）

算法原理

从任意顶点 i 到任意顶点 j 的最短路径不外乎有两种可能：

①、直接从 i 到 j

②、从 i 经过若干个顶点到 j

假设 dist(i, j) 为顶点 i 到顶点 j 的最短路径的距离

对于每一个顶点 k ，检查 dist(i, k) + dist(k, j) < dist(i, j) 是否成立

如果成立，证明从 i 到 k 再到 j 的路径比 i 直接到 j 的路径短，设置 dist(i, j) = dist(i, k) + dist(k, j)
当我们遍历完所有节点 k ，dist(i, j) 中记录的便是 i 到 j 的最短路径的距离

伪代码如下：

for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
			if (dist(i, k) + dist(k, j) < dist(i, j)) {
                dist(i, j) = dist(i, k) + dist(k, j);
            }
        } 
    }
}

4.2 编码实现

在编码实现之前，首先得明白什么叫做 “ 多源最短路径算法 ” ，理解了这个概念后，才可以编写正确的接口。

所谓 “ 多源最短路径算法 ” 指的就说从图中的每一个顶点出发，到其他顶点的最短路径的算法。

在 “ 单源最短路径算法 ” 中，我们的接口方法是Map<V, PathInfo<V, E>> shortestPath(V begin)，表示源点 begin 到 value 为 V 的顶点的最短路径信息是 PathInfo<V, E> 类型的。

但是对于 “ 多源最短路径算法 ” 来说，源点是有多个的，并不是只有一个，因此接口方法就可以不用传递参数。既然源点不止一个，那么如何返回不同源点的最短路径信息呢？

初看似乎很难，实则很简单。不同的源点到达不同的顶点对应了不同的最短路径信息 ，因此可以在单源最短路径算法接口返回值类型的基础上套一层 Map ，最终得到在Graph接口下的 “ 多源最短路径算法 ” 接口方法如下：

1 2	// 多源最短路径 public abstract Map<V, Map<V, PathInfo<V, E>>> shortestPath();

接口方法编写完成后，前往ListGraph类实现刚编写的接口方法。

在实现接口时需要先实例一个返回值类型的 HashMap ，最后的返回数据就是实例化的这个 HashMap。

初始化后，这个 Map 内是没有任何数据的，我们待会需要从这个 Map 中提取数据，因此还需要对这个 Map 进行初始化，初始化 Map 就是将图中每一条边都放到这个 Map 中。

初始化完成后，使用伪代码一样的逻辑将真正的代码编写出来，注意空值判断 。

伪代码逻辑遍历图中的顶点，需要进行三层遍历，每次遍历可以拿到一个顶点，总共三个顶点。这三个顶点可以确定三条边，需要注意的是这三个顶点任意两个不能相同，如果存在相同，确定的边就只有一条，为了避免这种情况，需要在遍历内部加上顶点相同判断 。

这三个顶点的任意两个顶点之间可能不存在直接相连的边，因此还需要注意空边的情况 。

@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) {
        // edge.from.value 作为起点到 V 之间的路径信息
        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) || v1.equals(v3) || v2.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<>();
                    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);
}