Java图论：弗洛伊德和迪杰斯特拉算法解决最短路径问题

在图论中，最短路径问题是指在一张图中，从起始点到终点的所有路径中，具有最小路径权值的路径。本文将介绍Java语言中如何使用弗洛伊德和迪杰斯特拉算法解决最短路径问题。

弗洛伊德算法

弗洛伊德算法（Floyd算法）是一种通过动态规划解决所有最短路径的算法。该算法的时间复杂度为O(n^3)，因此对于大型图而言，可能不太适用。

下面是Java中使用弗洛伊德算法解决最短路径问题的代码示例：

public class Floyd {

    public static void floyd(int[][] graph) {

        int V = graph.length;

        int[][] dist = new int[V][V];

        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[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];
                    }
                }
            }
        }

        printSolution(dist);
    }

    public static void printSolution(int[][] dist) {
        int V = dist.length;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] == Integer.MAX_VALUE) {
                    System.out.print("INF ");
                }
                else {
                    System.out.print(dist[i][j] + "   ");
                }
            }
            System.out.println();
        }
    }

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

上述代码中，我们定义了一个floyd()函数，它接收一个邻接矩阵作为输入，并输出所有顶点之间的最短距离。我们首先初始化dist数组为输入的邻接矩阵。

接着，我们通过三重循环遍历所有的顶点，并尝试将经过k点的路径加入到i和j之间的路径中。如果新路径的权值更小，则更新dist数组。最后输出所有的顶点之间的最短路径。

我们在main函数中调用函数，并传入我们自定义的邻接矩阵graph。

迪杰斯特拉算法

迪杰斯特拉算法（Dijkstra算法）是一种解决图的单源最短路径的贪心算法。该算法的时间复杂度为O(V^2)，其中V是图中所有顶点的数量。

下面是Java中使用迪杰斯特拉算法解决最短路径问题的代码示例：

import java.util.*;

public class Dijkstra {

    public void dijkstra(int[][] graph, int src) {
        int V = graph.length;
        int[] dist = new int[V];
        boolean[] sptSet = new boolean[V];

        for (int i = 0; i < V; i++) {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }
        dist[src] = 0;

        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, sptSet);
            sptSet[u] = true;
            for (int v = 0; v < V; v++) {
                if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        printSolution(dist, V);
    }

    public int minDistance(int[] dist, boolean[] sptSet) {
        int V = dist.length;
        int minIndex = -1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < V; i++) {
            if (!sptSet[i] && dist[i] <= min) {
                min = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    public void printSolution(int[] dist, int V) {
        System.out.println("Vertex   Distance from Source");
        for (int i = 0; i < V; i++) {
            System.out.println(i + "   " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                         {4, 0, 8, 0, 0, 0, 0, 11, 0},
                         {0, 8, 0, 7, 0, 4, 0, 0, 2},
                         {0, 0, 7, 0, 9, 14, 0, 0, 0},
                         {0, 0, 0, 9, 0, 10, 0, 0, 0},
                         {0, 0, 4, 14, 10, 0, 2, 0, 0},
                         {0, 0, 0, 0, 0, 2, 0, 1, 6},
                         {8, 11, 0, 0, 0, 0, 1, 0, 7},
                         {0, 0, 2, 0, 0, 0, 6, 7, 0}};
        Dijkstra dj = new Dijkstra();
        dj.dijkstra(graph, 0);
    }
}

上述代码中，我们定义了一个dijkstra()函数，它接受一个邻接矩阵以及起始顶点作为输入，并输出每个顶点到起始顶点的最短距离。我们首先初始化一个dist数组和sptSet数组，分别表示每个顶点到起始顶点的当前距离和是否已经被遍历。

接着，在每次循环中，我们选择一个距离起始顶点最近的顶点，并将其标记为已遍历。然后遍历该顶点的所有邻居，并将它们的距离更新为它们与当前顶点的距离加上当前顶点到起始顶点的距离。最后输出每个顶点到起始顶点的最短距离。

我们在main函数中调用函数，并传入我们自定义的邻接矩阵graph和起始顶点编号0（起始顶点可以是任意点）。