如何实现Dijkstra最短路径算法？

Dijkstra 算法是一种找到图中所有节点到某个节点的最短路径的算法。

我们可以使用邻接矩阵实现 Dijkstra 算法:

public int[] dijkstra(int[][] graph, int start) {
    int n = graph.length;
    boolean[] visited = new boolean[n];
    int[] dist = new int[n];
    for (int i = 0; i < n; i++) dist[i] = Integer.MAX_VALUE;

    dist[start] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        int min = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min) {
                u = j;
                min = dist[j];
            } 
        }

        if (u == -1) break;
        visited[u] = true;

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

    return dist;
}

算法流程:

1. 构建一个数组 dist 记录所有节点到 start 节点的距离,初始为 MAX_VALUE。start 节点距离为 0。
2. 找出当前未访问节点中 dist 最小的节点 u。如果所有节点都访问过则结束。
3. 标记 u 节点为已访问。
4. 更新 u 节点的未访问邻节点的距离。dist[v] = min(dist[v], dist[u] + graph[u][v])。
5. 重复步骤 2-4,直到所有节点都访问过。
6. 返回 dist 数组,即所有节点到 start 节点的最短距离。

时间复杂度 O(n^2),空间复杂度 O(n)。

所以,Dijkstra 算法的关键是:

1. 构建数组 dist 记录所有节点到起点的最短距离,初始为最大值。
2. 选取未访问节点中 dist 最小的节点 u。
3. 更新 u 的未访问邻节点的距离。dist[v] = min(dist[v], dist[u] + graph[u][v])。
4. 重复步骤 2 和 3,直到所有节点都访问过。
5. 返回 dist 数组,得到所有节点到起点的最短路径。