用java设计单源最短路径

在Java中，我们可以使用Dijkstra算法或者Floyd-Warshall算法来设计一个解决单源最短路径问题的程序。这里我们以Dijkstra算法为例，它是最常用的求解这个问题的有效方法。

Dijkstra算法步骤大致如下：

1. **初始化**：创建一个距离数组，将所有节点的距离设置为无穷大（通常使用整数最大值），起点（源节点）的距离设为0。

2. **优先队列**：使用最小堆（PriorityQueue）存储待处理的节点，初始只包含起点，并将其插入堆中。

3. **迭代过程**：直到堆为空或找到终点：
- 弹出当前节点，更新其邻居节点的距离，如果通过这个节点到达邻居的距离比已知更短，则更新邻居节点的距离，并将其加入堆中。

4. **路径跟踪**：当终点被找到并且其距离已经被标记为非负，说明找到了最短路径。从终点开始回溯，记录下每一步的前驱节点，直到起点。

以下是简单的Java代码框架示例：

import java.util.*;

public class Dijkstra {
    private List<Node> graph;
    // ...其他辅助数据结构和方法...

    public List<Node> dijkstra(Node start) {
        PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> a.distance - b.distance);
        Node[] distances = new Node[graph.size()];
        Arrays.fill(distances, null);
        distances[start.index] = start; // 设置起始点距离为0

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            if (current == endNode) break;

            for (Edge edge : current.edges) {
                int distance = current.distance + edge.weight;
                if (distances[edge.toIndex] == null || distance < distances[edge.toIndex].distance) {
                    distances[edge.toIndex] = new Node(edge.to, distance);
                    queue.offer(distances[edge.toIndex]);
                }
            }
        }

        return buildPath(start, distances[endNode.index]);
    }

    private List<Node> buildPath(Node start, Node end) {
        List<Node> path = new ArrayList<>();
        Node current = end;
        while (current != null) {
            path.add(current);
            current = current.prev;
        }
        Collections.reverse(path);
        return path;
    }
}

在这个例子中，`Node`代表图中的一个节点，包含索引、邻接边以及到目标节点的距离等信息；`Edge`表示连接两个节点的边，包含权重。