← 返回题目列表
UNSW COMP2521 · 中等

BFS · 无权最短距离

BFS · 求两点间最短边数

读入一张无向图和两个顶点 s、t,输出从 s 到 t 的最短路径长度(最少经过几条边)。不可达输出 -1;s == t 时输出 0。

这是 BFS 最招牌的用途:在无权图里,BFS 第一次到达某点时走的就是最短路。请补全 shortestDist。

易错点:① 用 dist[] 数组(初值 -1)兼当 visited 用:dist[w] < 0 表示还没访问。② 第一次给 dist[w] 赋值时 dist[w] = dist[v] + 1,之后别再改它(第一次到达即最短)。③ 必须用队列(先进先出);用栈就成了 DFS,最短路保证失效。

输入

  • 第 1 行:V E。
  • 接下来 E 行:每行 u v,表示无向边。
  • 最后一行:s t(起点、终点)。

输出

  • 一行:s 到 t 的最短边数;不可达为 -1。

示例:输入 4 3 / 0 1 / 1 2 / 2 3 / 0 3 → 输出 3(0→1→2→3)。