题目链接

题目描述

给定由 个顶点、 条边构成的有向无权图（不一定连通，允许重边，无自环）。给定起点 ，需要输出从 到每个顶点的最短路径长度；若不可达则输出 。

解题思路

  • 无权图最短路 = BFS：在无权图中，从单源 到各点的最短路长度可用广度优先搜索（BFS）在线性时间求出。
  • 具体做法：
    • 建立邻接表，距离数组 初始化为 ，令 。
    • 用队列按层推进：弹出当前点 ，遍历所有出边 ，若 ，则令 并入队。
    • 结束后按顶点编号从 到 输出 。
  • 正确性：BFS 按“层数”逐层扩展，首次到达某点即为最短路。
  • 复杂度：时间 ，空间 。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
    }
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (i > 1) cout << ' ';
        cout << dist[i];
    }
    cout << '\n';
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int s = sc.nextInt();
        List<Integer>[] g = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            g[u].add(v);
        }
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        ArrayDeque<Integer> q = new ArrayDeque<>();
        dist[s] = 0; q.add(s);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : g[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.add(v);
                }
            }
        }
        StringBuilder out = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i > 1) out.append(' ');
            out.append(dist[i]);
        }
        System.out.println(out);
    }
}

from collections import deque

n, m, s = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)

dist = [-1] * (n + 1)
q = deque()
dist[s] = 0
q.append(s)

while q:
    u = q.popleft()
    for v in g[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + 1
            q.append(v)

print(' '.join(str(dist[i]) for i in range(1, n + 1)))

算法及复杂度

  • 算法：对有向无权图以 为源点做 BFS，得到 。
  • 时间复杂度：。
  • 空间复杂度：。