单源最短路径问题java

单源最短路径问题是指在一个加权有向图中，给定一个起始节点，求出从起始节点到其他所有节点的最短路径。这个问题可以使用Dijkstra算法或者Bellman-Ford算法解决。

下面是使用Java实现Dijkstra算法的示例代码：

import java.util.*;

public class DijkstraAlgorithm {
    
    private int[][] graph;  // 图的邻接矩阵
    private int n;  // 图中节点的数量
    
    public DijkstraAlgorithm(int[][] graph) {
        this.graph = graph;
        this.n = graph.length;
    }
    
    // Dijkstra算法
    public int[] shortestPath(int start) {
        int[] dist = new int[n];  // 存储起始节点到每个节点的最短距离
        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;  // u表示离起始节点最近的未访问节点的下标
            int minDist = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    u = j;
                    minDist = dist[j];
                }
            }
            visited[u] = true;  // 标记节点u已被访问
            
            // 更新与节点u相邻的节点的距离
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0) {  // 如果节点v未被访问且与u相邻
                    dist[v] = Math.min(dist[v], dist[u] + graph[u][v]);  // 更新起始节点到节点v的距离
                }
            }
        }
        
        return dist;
    }
    
    public static void main(String[] args) {
        int[][] graph = {{0, 2, 4, 0, 0},
                         {0, 0, 1, 4, 2},
                         {0, 0, 0, 0, 3},
                         {0, 0, 0, 0, 0},
                         {0, 0, 0, 3, 0}};
        DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph);
        int[] dist = dijkstra.shortestPath(0);
        System.out.println(Arrays.toString(dist));  // 输出起始节点到其他节点的最短距离
    }
}

上面的代码中，graph表示要处理的加权有向图的邻接矩阵，n表示图中节点的数量。shortestPath方法接受一个起始节点的下标start作为参数，并返回一个数组dist，其中dist[i]表示起始节点到节点i的最短距离。

在Dijkstra算法的实现中，首先需要初始化dist数组为无穷大，然后将起始节点到自身的距离设为0。接下来，对于每个未访问的节点，找到距离起始节点最近的节点u，并将其标记为已访问。然后，遍历与节点u相邻的节点v，如果节点v未被访问且与u相邻，则更新起始节点到节点v的距离。重复这个过程，直到所有节点都被访问。

使用上面的示例代码可以很容易地处理单源最短路径问题。