Java利用Dijkstra和Floyd分别求取图的最短路径

Java 利用 Dijkstra 和 Floyd 算法分别求取图的最短路径可以分为以下几个步骤：

1. 建立图的数据结构

首先需要建立用于表示图的数据结构，通常可以使用邻接矩阵或邻接表来表示图。

以邻接矩阵为例，可以定义一个二维数组来表示图，数组中的每一个元素 a[i][j] 表示从节点 i 到节点 j 的边的权值。如果不存在从节点 i 到节点 j 的边，则 a[i][j] 的值设置为一个很大的数（如99999999）或者无穷大。

public class Graph {
    private int[][] edges;  // 图的邻接矩阵
    private int numVertices; // 图中节点的个数

    // 构造函数
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        edges = new int[numVertices][numVertices];
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                edges[i][j] = 0; // 初始化矩阵元素为0
            }
        }
    }

    // 添加一条边
    public void addEdge(int source, int destination, int weight) {
        edges[source][destination] = weight;
    }

    // 获取邻接矩阵
    public int[][] getMatrix() {
        return edges;
    }
}

2. Dijkstra 算法求最短路径

Dijkstra 算法是一种单源最短路径算法。它以一个节点为起点，依次计算出到其他节点的最短路径。

Dijkstra 算法的基本思想是：先将起点到各个点之间的距离初始化为 ∞，再通过松弛操作逐一更新各个节点的距离。

在 Dijkstra 算法的过程中，需要维护一个集合 S，存储已经确定了最短距离的节点；同时也需要维护一个数组 dist，dist[v] 表示从起点 s 到节点 v 的最短距离。

public class Dijkstra {
    public static void dijkstra(Graph graph, int source) {
        int[][] edges = graph.getMatrix();
        int numVertices = graph.getNumVertices();
        boolean[] visited = new boolean[numVertices]; // 标记节点是否已经加入集合S
        int[] dist = new int[numVertices]; // 存储从源点到其他节点的最短距离

        // 初始化 dist 数组
        for (int i = 0; i < numVertices; i++) {
            dist[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }

        // 把起点加入集合 S
        dist[source] = 0;

        // 循环直到所有节点都被加入集合 S
        for (int count = 0; count < numVertices - 1; count++) {
            // 在未加入集合 S 的节点中找到距离起点最近的节点
            int u = minDistance(dist, visited);

            // 把节点 u 加入集合 S
            visited[u] = true;

            // 更新 u 的邻接节点的距离
            for (int v = 0; v < numVertices; v++) {
                if (!visited[v] && edges[u][v] != 0 && 
                    dist[u] != Integer.MAX_VALUE && 
                    dist[u] + edges[u][v] < dist[v]) {
                    dist[v] = dist[u] + edges[u][v];
                }
            }
        }

        // 输出最短距离
        for (int i = 0; i < numVertices; i++) {
            System.out.printf("从 %d 到 %d 的最短距离是 %d\n",
                    source, i, dist[i]);
        }
    }

    // 找到未加入集合 S 的节点中距离起点最近的节点
    private static int minDistance(int[] dist, boolean[] visited) {
        int min = Integer.MAX_VALUE, minIndex = -1;

        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] <= min) {
                min = dist[i];
                minIndex = i;
            }
        }

        return minIndex;
    }
}

3. Floyd 算法求最短路径

Floyd 算法是一种多源最短路径算法，它可以计算出任意两个节点之间的最短距离。

Floyd 算法的基本思想是：对于图中的每个节点，求出它与其他节点之间的最短路径。算法采用动态规划的思想，通过一个矩阵来记录任意两个节点之间的最短距离。

public class Floyd {
    public static void floyd(Graph graph) {
        int[][] edges = graph.getMatrix();
        int numVertices = graph.getNumVertices();

        // 构造一个与边权矩阵大小相同的数组，初始为边权矩阵
        int[][] shortestPaths = new int[numVertices][numVertices];

        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                shortestPaths[i][j] = edges[i][j];
            }
        }

        // 通过中间节点 k 来更新最短路径
        for (int k = 0; k < numVertices; k++) {
            for (int i = 0; i < numVertices; i++) {
                for (int j = 0; j < numVertices; j++) {
                    if (shortestPaths[i][k] + shortestPaths[k][j] < shortestPaths[i][j]) {
                        shortestPaths[i][j] = shortestPaths[i][k] + shortestPaths[k][j];
                    }
                }
            }
        }

        // 输出最短距离
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                System.out.printf("从 %d 到 %d 的最短距离是 %d\n",
                        i, j, shortestPaths[i][j]);
            }
        }
    }
}

4. 示例说明

假设有如下图形：

     1
(0)--(1)--(2)
 |   / \   |
6|  /   \  |5
 | /     \ |
(3)-------(4)    9
       2   

使用邻接矩阵表示该图：

    0   1   2   3   4  
0   0   1   6   0   0  
1   1   0   5   2   7  
2   6   5   0   0   3  
3   0   2   0   0   4  
4   0   7   3   4   0  

如果以节点 0 为起点，采用 Dijkstra 算法，则最短路径为：

从 0 到 0 的最短距离是 0
从 0 到 1 的最短距离是 1
从 0 到 2 的最短距离是 6
从 0 到 3 的最短距离是 8
从 0 到 4 的最短距离是 15

如果采用 Floyd 算法，则最短路径为：

从 0 到 0 的最短距离是 0
从 0 到 1 的最短距离是 1
从 0 到 2 的最短距离是 6
从 0 到 3 的最短距离是 8
从 0 到 4 的最短距离是 15
从 1 到 0 的最短距离是 1
从 1 到 1 的最短距离是 0
从 1 到 2 的最短距离是 5
从 1 到 3 的最短距离是 2
从 1 到 4 的最短距离是 7
从 2 到 0 的最短距离是 6
从 2 到 1 的最短距离是 5
从 2 到 2 的最短距离是 0
从 2 到 3 的最短距离是 6
从 2 到 4 的最短距离是 3
从 3 到 0 的最短距离是 8
从 3 到 1 的最短距离是 2
从 3 到 2 的最短距离是 6
从 3 到 3 的最短距离是 0
从 3 到 4 的最短距离是 4
从 4 到 0 的最短距离是 15
从 4 到 1 的最短距离是 7
从 4 到 2 的最短距离是 3
从 4 到 3 的最短距离是 4
从 4 到 4 的最短距离是 0