Java实现最短路径算法

在 Java 中实现最短路径算法，你可以使用经典的Dijkstra算法或者A*算法。这里我给你一个使用Dijkstra算法的示例代码：

import java.util.*;

public class DijkstraAlgorithm {
    private int V;
    private int[][] graph;

    public DijkstraAlgorithm(int[][] graph) {
        this.V = graph.length;
        this.graph = graph;
    }

    public int[] findShortestPath(int source) {
        int[] dist = new int[V]; // 存储源节点到各个节点的最短距离
        boolean[] visited = new boolean[V]; // 标记节点是否已被访问

        Arrays.fill(dist, Integer.MAX_VALUE); // 初始化距离为无穷大
        dist[source] = 0; // 源节点到自身的距离为0

        for (int count = 0; count < V - 1; count++) {
            int u = findMinimumDistance(dist, visited);
            visited[u] = true;

            for (int v = 0; v < V; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                        && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        return dist;
    }

    private int findMinimumDistance(int[] dist, boolean[] visited) {
        int minDist = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int v = 0; v < V; v++) {
            if (!visited[v] && dist[v] <= minDist) {
                minDist = dist[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    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}
        };

        DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph);
        int[] shortestDistances = dijkstra.findShortestPath(0);

        System.out.println("最短路径：");
        for (int i = 1; i < shortestDistances.length; i++) {
            System.out.println("从节点 " + source + " 到节点 " + i + " 的最短距离为：" + shortestDistances[i]);
        }
    }
}

这个示例代码使用邻接矩阵来表示图，其中图的顶点数由变量 V 来表示，图的边权重由二维数组 graph 来表示。你可以根据自己的需求修改图的结构。

在示例代码中，`findShortestPath` 方法使用了 Dijkstra 算法来计算从源节点到其他所有节点的最短路径。`main` 方法展示了如何使用这个算法来计算最短路径并输出结果。

希望这个示例代码能帮助到你！如果你对其他算法或者实现有疑问，请随时提问。