結(jié)合前面的Dijkstra算法或者Bellman-Ford算法，其實也可以計算出任意兩個頂點之間的最短路徑。例如下圖

以Dijkstra為例：

如果要計算出任意兩個頂點之間的最短路徑，其實可以遍歷所有的頂點，對每一個頂點做一次Dijkstra操作，其實也可以計算出任意兩個頂點之間的最短路徑。

是的，上面這種做法，是計算任意兩個頂點之間最短路徑的一種做法，不過現(xiàn)在有比這種做法更好的另外一種做法，那就是使用Floyd來實現(xiàn)。

Floyd

Floyd屬于多源最短路徑算法，能夠求出任意兩個頂點之間的最短路徑，支持負權(quán)邊。

Floyd的時間復(fù)雜度：O(V^3)，效率比執(zhí)行V次Dijkstra算法要好（V是頂點數(shù)量）

算法原理

• 從任意頂點i到任意頂點j的最短路徑不外乎兩種可能
  1. 直接從i到j(luò)
  2. 從i經(jīng)過若干個頂點到j(luò)
• 現(xiàn)假設(shè)有一種狀態(tài)dist(i,j)，為頂點i到頂點j的最短路徑距離
  • 對于每一個頂點k，都要執(zhí)行dist(i,k) + dist(k,j) < dist(i,j)是否成立
    • 如果成立，證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，就更新dist(i,j) = dist(i,k) + dist(k,j)
    • 當遍歷完所有的頂點k，dist(i,j) 中記錄的邊是i到j(luò)的最短路徑距離

所以，結(jié)合上面的算法原理，可以分析得到Floyd算法的偽代碼

public void floyd(V v) {
    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);
                }
            }
        }
    }
}

所以，可以發(fā)現(xiàn)，上面的偽代碼非常簡答， 并且只需要將上面的偽代碼轉(zhuǎn)換為基于ListGraph的代碼即可

最終得到的實現(xiàn)代碼如下

public Map<V, Map<V, PathInfo<V, E>>> shortestPath() {
        Map<V, Map<V, PathInfo<V, E>>> paths = new HashMap<>();
        //初始化,將最開始能走的邊都初始化paths中
        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);
    }

demo下載地址

完！