图的最短路径算法java

常见的图的最短路径算法有 Dijkstra 算法和 Floyd 算法。下面给出两种算法的 Java 实现。

Dijkstra 算法：

import java.util.Arrays;

public class DijkstraAlgorithm {

    private static final int INF = Integer.MAX_VALUE; // 代表两个节点之间没有连边

    public static void dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n]; // 存储起点到各个节点的最短路径长度
        boolean[] visited = new boolean[n]; // 记录节点是否已经被访问过
        Arrays.fill(dist, INF);
        dist[start] = 0;

        for (int i = 0; i < n - 1; i++) {
            int minDist = INF;
            int minIndex = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    minIndex = j;
                }
            }
            if (minIndex == -1) {
                break;
            }
            visited[minIndex] = true;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && graph[minIndex][j] != INF) {
                    dist[j] = Math.min(dist[j], dist[minIndex] + graph[minIndex][j]);
                }
            }
        }

        System.out.println("从节点 " + start + " 出发，到各个节点的最短距离为：");
        for (int i = 0; i < n; i++) {
            System.out.println(start + " -> " + i + " : " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 2, 1, 4, INF},
                {2, 0, 4, 2, 3},
                {1, 4, 0, 1, 2},
                {4, 2, 1, 0, 3},
                {INF, 3, 2, 3, 0}
        };
        dijkstra(graph, 0);
    }
}

Floyd 算法：

import java.util.Arrays;

public class FloydAlgorithm {

    private static final int INF = Integer.MAX_VALUE;

    public static void floyd(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n]; // 存储任意两个节点之间的最短路径长度
        int[][] path = new int[n][n]; // 存储任意两个节点之间的最短路径的前驱节点
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
                if (graph[i][j] != INF && i != j) {
                    path[i][j] = i;
                } else {
                    path[i][j] = -1;
                }
            }
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        path[i][j] = path[k][j];
                    }
                }
            }
        }

        System.out.println("任意两个节点之间的最短路径长度为：");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(dist[i][j] + "\t");
            }
            System.out.println();
        }

        System.out.println("任意两个节点之间的最短路径为：");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || dist[i][j] == INF) {
                    continue;
                }
                System.out.print(i);
                int p = path[i][j];
                while (p != j) {
                    System.out.print(" -> " + p);
                    p = path[p][j];
                }
                System.out.println(" -> " + j);
            }
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 2, INF, 4, INF},
                {INF, 0, 4, INF, INF},
                {1, INF, 0, 1, INF},
                {INF, INF, 2, 0, 3},
                {INF, INF, INF, INF, 0}
        };
        floyd(graph);
    }
}

以上就是 Dijkstra 算法和 Floyd 算法的 Java 实现，其中 INF 表示两个节点之间没有连边，可以自行修改。