洛谷 P4779 单源最短路径
Dijkstra 算法，解决 有向 非负权图 的单源最短路径算法。
import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; /** * @author wangshaoyu */ public class Main { // 快速输入输出 static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out)); static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer st = new StreamTokenizer(br); static int nextInt() throws IOException { st.nextToken(); return (int)st.nval; } static ArrayList<Edge>[] adj; // 邻接表结构存储顶点的数组 static Edge[] edgeTo; static int[] distTo; static PriorityQueue<Pair> pq; // 存放 distTo[index] 的值 static boolean[] visited; // 用于标记到达某个点的的最短路径是否已经找到 public static void main(String[] args) throws IOException { int n = nextInt(); // n 个顶点 int m = nextInt(); // m 条边 int start = nextInt() - 1; // 源点 // 建图 adj = new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); } // 注意：下标从0开始 for (int i = 0; i < m; i++) { int v = nextInt() - 1; int w = nextInt() - 1; int weight = nextInt(); adj[v].add(new Edge(v, w, weight)); } pq = new PriorityQueue<>(); edgeTo = new Edge[n]; distTo = new int[n]; visited = new boolean[n]; // 初始化 Arrays.fill(distTo, Integer.MAX_VALUE); distTo[start] = 0; pq.add(new Pair(start, 0)); // 加入源点 // 因为每次都从 pq 中找到最小的那个 distTo，所以可以用堆优化 // 为什么每次找到最小的distTo[w], 就是找到了源点到达 w 的最短路径？ // 因为我们是对 v-w 进行松弛操作（判断 distTo[w] > distTo[v] + e.weight），最小的 distTo 已经没办法再进行松弛操作了。 // 也就是说 v-w 这些边已经都失效了。已经不可能让 distTo[w] 更小了，所以最小的 distTo[w] 就是源点到 w 的最短路径。 while (! pq.isEmpty()) { Pair pair = pq.poll(); relax(pair.index); } // 输出 StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.append(distTo[i]).append(" "); } pw.println(sb.toString().trim()); pw.flush(); } // 边的松弛操作, 检查从源点 s 到 w 的最短路径是不是从 s 到 v 再到 w // distTo[] 只可能变小,单调递减。所以从顶点 w 的所有的前一个顶点 v 都进行松弛操作，就可以得出distTo[w] 的最小值（也就是源点到达 w 的最短路径）。 static void relax(int v) { // 因为在 pq 中会保留到达某个顶点的很多个 distTo，如果到达这个点的最短路径已经找到，那么这些距离就都失效了 if (visited[v] == true) { return; } visited[v] = true; for (Edge e : adj[v]) { int w = e.to(); // 说明 v-w 这条边是有效的，否则这条边失效了 if (distTo[w] > distTo[v] + e.weight) { distTo[w] = distTo[v] + e.weight; edgeTo[w] = e; // 添加进 pq pq.add(new Pair(w, distTo[w])); } } } } /** * 边结构 */ class Edge { int v; int w; int weight; public Edge(int v, int w, int weight) { this.v = v; this.w = w; this.weight = weight; } public int from() { return v; } public int to() { return w; } } /** * 堆结点 */ class Pair implements Comparable<Pair>{ int index; // dist : distTo[index] 的值 int dist; public Pair(int index, int dist) { this.index = index; this.dist = dist; } @Override public int compareTo(Pair o) { return this.dist - o.dist; } }