java实现dijkstra算法求有向图最短路径之和

Dijkstra算法可以用来解决有向图中单源最短路径问题。下面是使用Java实现Dijkstra算法求有向图最短路径之和的代码：

import java.util.*;

public class Dijkstra {
    private static int INF = Integer.MAX_VALUE; // 无穷大

    public static void main(String[] args) {
        int[][] graph = { // 有向图的邻接矩阵表示
            {0, 10, INF, 30, 100},
            {INF, 0, 50, INF, INF},
            {INF, INF, 0, INF, 10},
            {INF, INF, 20, 0, 60},
            {INF, INF, INF, INF, 0}
        };
        int[] dist = dijkstra(graph, 0); // 求从节点0到其他节点的最短路径
        System.out.println(Arrays.toString(dist)); // 输出结果
    }

    public static int[] dijkstra(int[][] graph, int source) {
        int n = graph.length; // 图中节点的个数
        int[] dist = new int[n]; // 存储从源点到各个节点的最短距离
        boolean[] visited = new boolean[n]; // 标记是否已经访问过该节点
        Arrays.fill(dist, INF); // 初始化最短距离为无穷大
        dist[source] = 0; // 源点到自身的距离为0

        for (int i = 0; i < n - 1; i++) { // Dijkstra算法的核心部分
            int u = -1; // u表示当前距离源点最近的节点
            int minDist = INF; // minDist存储当前最短距离

            for (int j = 0; j < n; j++) { // 找出当前距离源点最近的节点
                if (!visited[j] && dist[j] < minDist) {
                    u = j;
                    minDist = dist[j];
                }
            }

            visited[u] = true; // 标记该节点已经访问过

            for (int v = 0; v < n; v++) { // 更新最短距离
                if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        return dist;
    }
}

上述代码中的图是以下图形式给出的：

0 --(10)--> 1 --(50)--> 2 --(10)--> 4
|           ^           |           ^
v           |           v           |
3 --(30)--> 2 --(20)--> 3 --(60)--> 4

代码中采用邻接矩阵表示有向图，其中`graph[i][j]`表示从节点`i`到节点`j`的边权重，如果该边不存在，则权重为无穷大。

Dijkstra算法的核心部分是在每次迭代中找到距离源点最近的未访问节点，然后更新与该节点相邻的节点的最短距离。在本例中，我们使用`visited`数组来标记是否已经访问过该节点，使用`dist`数组来存储从源点到各个节点的最短距离。