java Dijkstra算法

Dijkstra算法是一种用于解决带权重图的单源最短路径问题的贪心算法。它的基本思想是从起点开始，每次选择当前最短路径的节点进行扩展，直到扩展到终点为止。下面是Dijkstra算法的基本步骤：

1. 初始化：将起点s到所有节点的距离dist[s]初始化为0，将其他节点的距离dist[v]初始化为无穷大。
2. 选择当前距离起点最近的节点u，并标记u为已访问。
3. 对于u的每个邻居节点v，如果从起点s到v的距离dist[v]大于从起点s到u再到v的距离dist[u]+w(u,v)，则更新dist[v]=dist[u]+w(u,v)。
4. 重复步骤2和3，直到所有节点都被访问或者终点t被访问。

下面是一个Java实现的例子：

import java.util.*;

public class Dijkstra {
    public static void main(String[] args) {
        int[][] graph = {{0, 10, 3, Integer.MAX_VALUE},
                         {Integer.MAX_VALUE, 0, 1, Integer.MAX_VALUE},
                         {Integer.MAX_VALUE, 4, 0, 2},
                         {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}};
        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];
        boolean[] visited = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 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] != Integer.MAX_VALUE) {
                    dist[v] = Math.min(dist[v], dist[u] + graph[u][v]);
                }
            }
        }
        return dist;
    }
}