Floyd-Warshall算法

Floyd-Warshall算法是一种解决所有对之间最短路径问题的动态规划算法，适用于有向图和无向图，包括带有负权重边的图（但不允许负权重环）。该算法可以在$O(|V{|}^3)$的时间复杂度内找到图中任意两点之间的最短路径，其中$|V|$是顶点的数量。

基本思想

Floyd-Warshall算法通过动态规划的方法，逐步构建一个矩阵，其中每个元素$d_{ij}^k$代表从顶点$i$到顶点$j$，并且只允许经过顶点集$\{1,2,\dots ,k\}$中的顶点作为中间顶点的最短路径长度。通过不断地增加中间顶点的数量，最终得到所有顶点对之间的最短路径。

算法步骤

1. 初始化：

   • 创建一个二维数组dis，其中dis[i][j]表示从顶点$i$到顶点$j$的初始最短路径长度。如果两个顶点之间没有直接相连的边，则设为无穷大。
   • 如果$i==j$，则dis[i][j] = 0。

2. 动态规划：

   • 对于每个可能的中间顶点$k$（从1到$|V|$），更新所有顶点对之间的最短路径。具体来说，对于每一对顶点$i$和$j$，检查是否存在一个更短的路径通过顶点$k$：$$d_{ij}^k=min(d_{ij}^{k-1},d_{ik}^{k-1}+d_{kj}^{k-1})$$其中，$d_{ij}^k$表示通过顶点$k$作为中间顶点的最短路径长度。

3. 检测负权重环：

   • 如果存在一个顶点$i$使得$d_{ii}<0$，则说明存在一个负权重环，因为从一个顶点到它自己最短路径不可能小于零。

代码实现

查看代码

import java.util.Arrays;

public class FloydWarshall {

    public void floydWarshall(int[][] graph) {
        int numVertices = graph.length;
        int[][] dis = new int[numVertices][numVertices];
        boolean hasNegativeCycle = false;

        // 初始化距离矩阵
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (graph[i][j] == 0 && i != j) {
                    dis[i][j] = Integer.MAX_VALUE; // 如果没有直接边，则设为无穷大
                } else {
                    dis[i][j] = graph[i][j];
                }
            }
        }

        // 动态规划
        for (int k = 0; k < numVertices; k++) {
            for (int i = 0; i < numVertices; i++) {
                for (int j = 0; j < numVertices; j++) {
                    if (dis[i][k] != Integer.MAX_VALUE && dis[k][j] != Integer.MAX_VALUE &&
                            dis[i][k] + dis[k][j] < dis[i][j]) {
                        dis[i][j] = dis[i][k] + dis[k][j];
                    }
                }
            }
        }

        // 检测负权重环
        for (int i = 0; i < numVertices; i++) {
            if (dis[i][i] < 0) {
                hasNegativeCycle = true;
                break;
            }
        }

        // 输出结果
        if (hasNegativeCycle) {
            System.out.println("存在负权重环！");
        } else {
            printSolution(dis, numVertices);
        }
    }

    private void printSolution(int[][] dis, int numVertices) {
        System.out.println("顶点对之间的最短路径:");
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (dis[i][j] == Integer.MAX_VALUE) {
                    System.out.print("INF ");
                } else {
                    System.out.print(dis[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 3, Integer.MAX_VALUE, 7},
            {8, 0, 2, Integer.MAX_VALUE},
            {5, Integer.MAX_VALUE, 0, 1},
            {2, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        };

        new FloydWarshall().floydWarshall(graph);
    }
}

代码解释

1. 初始化：创建一个二维数组dis来存储各个顶点之间的最短路径。如果两个顶点之间没有直接相连的边，则设为无穷大。
2. 动态规划：通过三层嵌套循环来更新每一对顶点之间的最短路径。
3. 检测负权重环：最后检查是否有顶点到自身的最短路径小于零，如果有，则存在负权重环。
4. 输出结果：如果存在负权重环，则输出提示信息；否则，输出所有顶点对之间的最短路径。

Johnson算法

Johnson算法是一种用于求解所有顶点对之间的最短路径问题的算法，特别适用于包含负权重边但不允许负权重环的图。Johnson算法结合了Bellman-Ford算法和Dijkstra算法的优点，首先使用Bellman-Ford算法来重新加权图中的边，从而将负权重边转换为非负权重边，然后再使用Dijkstra算法来计算最短路径。

基本思想

1. 添加超级源点：在原始图的基础上添加一个新的超级源点，并向所有其他顶点添加权重为0的边。
2. 重新加权边：使用Bellman-Ford算法从超级源点出发，计算所有顶点到其他顶点的最短路径。根据这些最短路径，重新调整边的权重，使得新的权重是非负的。
3. 运行Dijkstra算法：对于每个顶点，使用Dijkstra算法计算该顶点到所有其他顶点的最短路径。由于边的权重已经是非负的，所以Dijkstra算法适用。
4. 恢复原权重：最后，根据之前的最短路径计算结果，将路径长度恢复成原始图中的权重。

代码实现

查看代码

import java.util.Arrays;
import java.util.PriorityQueue;

public class JohnsonAlgorithm {

    private static final int INF = Integer.MAX_VALUE;

    // Bellman-Ford algorithm
    private void bellmanFord(int[][] graph, int numVertices, int source, int[] dis) {
        Arrays.fill(dis, INF);
        dis[source] = 0;

        // Relax all edges |V| - 1 times
        for (int i = 1; i <= numVertices - 1; i++) {
            for (int u = 0; u < numVertices; u++) {
                for (int v = 0; v < numVertices; v++) {
                    if (graph[u][v] != INF && dis[u] != INF && dis[u] + graph[u][v] < dis[v]) {
                        dis[v] = dis[u] + graph[u][v];
                    }
                }
            }
        }

        // Check for negative-weight cycles
        for (int u = 0; u < numVertices; u++) {
            for (int v = 0; v < numVertices; v++) {
                if (graph[u][v] != INF && dis[u] != INF && dis[u] + graph[u][v] < dis[v]) {
                    throw new IllegalArgumentException("Graph contains a negative-weight cycle");
                }
            }
        }
    }

    // Dijkstra's algorithm with priority queue
    private void dijkstra(int[][] graph, int numVertices, int source, int[] dis) {
        Arrays.fill(dis, INF);
        dis[source] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{source, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];

            for (int v = 0; v < numVertices; v++) {
                if (graph[u][v] != INF && dis[u] + graph[u][v] < dis[v]) {
                    dis[v] = dis[u] + graph[u][v];
                    pq.offer(new int[]{v, dis[v]});
                }
            }
        }
    }

    public void johnson(int[][] graph, int numVertices) {
        int numVerticesWithSuperSource = numVertices + 1;
        int[][] extendedGraph = new int[numVerticesWithSuperSource][numVerticesWithSuperSource];

        // Initialize the extended graph
        for (int i = 0; i < numVerticesWithSuperSource; i++) {
            Arrays.fill(extendedGraph[i], INF);
            extendedGraph[i][i] = 0;
        }

        // Add super source and connect it to all vertices
        for (int i = 0; i < numVertices; i++) {
            extendedGraph[numVertices][i] = 0;
        }

        // Copy original graph
        for (int i = 0; i < numVertices; i++) {
            System.arraycopy(graph[i], 0, extendedGraph[i], 0, numVertices);
        }

        // Run Bellman-Ford on the extended graph
        int[] h = new int[numVerticesWithSuperSource];
        bellmanFord(extendedGraph, numVerticesWithSuperSource, numVertices, h);

        // Re-weight the edges
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (extendedGraph[i][j] != INF) {
                    graph[i][j] += h[i] - h[j];
                }
            }
        }

        // Run Dijkstra for each vertex
        int[][] allPairsShortestPaths = new int[numVertices][numVertices];
        for (int i = 0; i < numVertices; i++) {
            int[] dis = new int[numVertices];
            dijkstra(graph, numVertices, i, dis);
            for (int j = 0; j < numVertices; j++) {
                allPairsShortestPaths[i][j] = dis[j] + h[j] - h[i];
            }
        }

        // Print the result
        printSolution(allPairsShortestPaths, numVertices);
    }

    private void printSolution(int[][] allPairsShortestPaths, int numVertices) {
        System.out.println("顶点对之间的最短路径:");
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (allPairsShortestPaths[i][j] == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print(allPairsShortestPaths[i][j] + " ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int numVertices = 4;
        int[][] graph = {
            {0, 3, Integer.MAX_VALUE, 7},
            {8, 0, 2, Integer.MAX_VALUE},
            {5, Integer.MAX_VALUE, 0, 1},
            {2, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        };

        new JohnsonAlgorithm().johnson(graph, numVertices);
    }
}

代码解释

1. 初始化扩展图：添加一个超级源点，并将超级源点连接到所有其他顶点。
2. 运行Bellman-Ford算法：计算从超级源点到所有顶点的最短路径，并使用这些路径来重新加权图中的边。
3. 运行Dijkstra算法：对于每个顶点，使用Dijkstra算法计算该顶点到所有其他顶点的最短路径。
4. 恢复原权重：根据之前的最短路径计算结果，将路径长度恢复成原始图中的权重。

Johnson算法的优点在于它能够有效地处理含有负权重边的图，同时保持较好的性能，尽管最坏情况的时间复杂度为$O(|V{|}^2\ast log|V|+|V|\ast |E|)$。