求有向图中某点到其他所有点的最短路径java

在Java中，求有向图中某个顶点到所有其他顶点的最短路径通常会使用Dijkstra算法或者Floyd-Warshall算法。这里以Dijkstra算法为例，因为它是最适合单源最短路径的问题：

import java.util.*;

public class ShortestPaths {
    private int V; // 图的顶点数
    private List<List<Integer>> adj; //邻接列表表示图
    private double[] dist; // 存储每个节点到起点的距离

    public ShortestPaths(int vertices) {
        this.V = vertices;
        adj = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; ++i)
            adj.add(new ArrayList<>());
    }

    // 添加边到图中
    public void addEdge(int src, int dest, int weight) {
        adj.get(src).add(dest);
    }

    // Dijkstra算法求解最短路径
    public void dijkstra(int src) {
        dist = new double[V];
        boolean[] visited = new boolean[V];

        Arrays.fill(dist, Double.POSITIVE_INFINITY);
        dist[src] = 0;

        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, visited);

            visited[u] = true;

            for (int v : adj.get(u)) {
                if (!visited[v] && dist[u] != Double.POSITIVE_INFINITY &&
                        dist[u] + graphWeight(u, v) < dist[v]) {
                    dist[v] = dist[u] + graphWeight(u, v);
                }
            }
        }
    }

    // 返回距离数组中最小值的索引
    private int minDistance(double[] dist, boolean[] visited) {
        int minIndex = -1;
        double minValue = Double.MAX_VALUE;

        for (int v = 0; v < V; v++)
            if (!visited[v] && dist[v] <= minValue)
                minIndex = v, minValue = dist[v];

        return minIndex;
    }

    // 计算两个节点间的实际权重
    private int graphWeight(int u, int v) {
        // 根据实际的边权重函数实现，这里是假设权重就是边的编号
        return adj.get(u).indexOf(v) + 1;
    }

    // 获取从src到其他所有点的最短距离
    public List<Double> getDistancesFromSrc(int src) {
        dijkstra(src);
        List<Double> result = new ArrayList<>();
        for (int i = 0; i < V; i++)
            result.add(dist[i]);
        return result;
    }

    public static void main(String[] args) {
        ShortestPaths sp = new ShortestPaths(5); // 示例5个顶点
        // 添加边...
        System.out.println(sp.getDistancesFromSrc(0)); // 输出从0到其他点的最短路径
    }
}

在这个示例中，`ShortestPaths` 类包含了Dijkstra算法的基本结构，包括初始化、添加边、计算最短路径等方法。`getDistancesFromSrc` 方法用于获取指定源点到所有其他点的最短路径。

注意：这个实现假设了图中边的权重是正整数，并且使用了邻接表来存储图。如果边的权重不是简单的整数，或者需要处理负权边，或者其他特定情况，可能需要调整 `graphWeight` 方法。