用java写一个最短路径

最短路径算法有很多种，其中比较经典的有迪杰斯特拉算法和弗洛伊德算法。下面我会给你介绍一下迪杰斯特拉算法的Java实现。

迪杰斯特拉算法是一种贪心算法，用于求解带权重的有向图或无向图的单源最短路径问题，其中权重可以是负数但不能存在负数权重的环路。迪杰斯特拉算法的基本思想是从起点开始，每次选择当前距离起点最近的一个顶点，并通过该顶点更新其他顶点的距离。算法的核心是维护一个距离数组，记录每个顶点到起点的最短距离。

下面是迪杰斯特拉算法的Java实现：

import java.util.*;

public class ShortestPath {
    public static void main(String[] args) {
        int n = 5;  // 图的节点数
        int[][] graph = {
                {0, 2, 1, 4, 5},
                {2, 0, 4, 2, 3},
                {1, 4, 0, 1, 2},
                {4, 2, 1, 0, 1},
                {5, 3, 2, 1, 0}
        };  // 图的邻接矩阵表示，graph[i][j]表示节点i到节点j的距离
        int start = 0;  // 起点
        int[] dist = dijkstra(graph, start);  // 计算最短路径
        System.out.println(Arrays.toString(dist));  // 输出结果
    }

    // 迪杰斯特拉算法
    public static int[] dijkstra(int[][] graph, int start) {
        int n = graph.length;  // 图的节点数
        int[] dist = new int[n];  // 距离数组，dist[i]表示起点到节点i的最短距离
        boolean[] visited = new boolean[n];  // 记录是否已访问过的数组
        Arrays.fill(dist, Integer.MAX_VALUE);  // 初始化距离数组为无穷大
        dist[start] = 0;  // 起点到自己的距离为0
        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                    u = j;  // 选择距离起点最近的未访问节点
                }
            }
            visited[u] = true;  // 标记该节点已访问
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];  // 通过u更新其他节点的距离
                }
            }
        }
        return dist;
    }
}

上述代码实现了一个简单的最短路径算法，可以对于给定的邻接矩阵，计算出从起点出发到每个节点的最短距离。