java实现dijkstra算法求最短路径

Dijkstra算法是一种经典的单源最短路径算法，可以用来求解无负权边的有向图或无向图中某个顶点到其他所有顶点的最短路径。下面是Java实现Dijkstra算法的示例代码：

import java.util.*;

public class Dijkstra {
    public static void main(String[] args) {
        int n = 5; // 顶点数量
        int[][] graph = {
            {0, 10, Integer.MAX_VALUE, 30, 100},
            {Integer.MAX_VALUE, 0, 50, Integer.MAX_VALUE, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 10},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, 20, 0, 60},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        }; // 图的邻接矩阵表示，用Integer.MAX_VALUE表示两个顶点之间没有边
        int start = 0; // 起点

        int[] dist = new int[n]; // 存储起点到各个顶点的最短距离
        boolean[] visited = new boolean[n]; // 标记各个顶点是否已经被访问过

        // 初始化距离数组
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // 运行Dijkstra算法
        for (int i = 0; i < n - 1; i++) {
            int u = -1; // u表示当前距离起点最近的未访问顶点
            int minDist = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    u = j;
                    minDist = dist[j];
                }
            }
            if (u == -1) break;
            visited[u] = true;
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != Integer.MAX_VALUE) {
                    dist[v] = Math.min(dist[v], dist[u] + graph[u][v]);
                }
            }
        }

        // 输出结果
        for (int i = 0; i < n; i++) {
            System.out.println("起点到顶点" + i + "的最短距离是：" + dist[i]);
        }
    }
}

在上面的代码中，我们使用了一个二维数组`graph`来表示图的邻接矩阵，其中`graph[i][j]`表示顶点i到顶点j之间的边的权重。如果两个顶点之间没有边，则用`Integer.MAX_VALUE`表示。`start`表示起点的编号。`dist`数组用于存储起点到各个顶点的最短距离，`visited`数组用于标记各个顶点是否已经被访问过。在算法运行过程中，我们首先将起点到自己的距离设为0，其余顶点的距离设为无穷大。然后，我们每次选择距离起点最近的未访问顶点，将其标记为已访问，并更新其邻居的距离。最后，输出起点到各个顶点的最短距离即可。