题解 | #【模板】单源最短路Ⅰ ‖ 无权图#

题目链接

【模板】单源最短路Ⅰ ‖ 无权图

题目描述

在一个有向无权图中，给定一个起始点，求它到图中所有顶点的最短路径长度。

解题思路

对于边权全部相等（或无权，可视为边权为1）的图，求解单源最短路径问题最适合使用广度优先搜索 (BFS)。

广度优先搜索 (BFS)

BFS 算法的特点是逐层遍历。它从源点开始，首先探索所有距离为 1 的邻居，然后是所有距离为 2 的邻居，以此类推。这种按距离逐层扩展的搜索方式，天然地保证了当算法第一次到达某个顶点时，所经过的路径就是从源点到该顶点的最短路径。

算法流程

数据结构：
- 一个队列，用于存储待访问的顶点。
- 一个邻接表 adj，用于存储图的结构。
- 一个距离数组 dist，用于存储源点到每个顶点的最短距离，并兼作访问标记。
初始化：
- 将 dist 数组的所有元素初始化为一个特殊值（例如 -1），表示所有顶点尚未被访问。
- 将源点 s 的距离 dist[s] 设为 0。
- 将源点 s 推入队列。
搜索过程：
- 当队列不为空时，循环执行以下操作： a. 从队列中取出一个顶点 u。 b. 遍历 u 的所有邻接点 v。 c. 如果 v 尚未被访问（即 dist[v] == -1），则： i. 更新 v 的距离：dist[v] = dist[u] + 1。 ii. 将 v 推入队列。
结束：
- 当队列为空时，搜索结束。dist 数组中就包含了从源点到所有可达顶点的最短路径长度。对于不可达的顶点，其距离值仍为初始值 -1。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, s;
    cin >> n >> m >> s;

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[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 : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << dist[i] << (i == n ? "" : " ");
    }
    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<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj.get(u).add(v);
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();

        dist[s] = 0;
        q.offer(s);

        while (!q.isEmpty()) {
            int u = q.poll();

            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.offer(v);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            System.out.print(dist[i] + (i == n ? "" : " "));
        }
        System.out.println();
    }
}

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    n, m, s = map(int, input().split())
    
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        adj[u].append(v)
        
    dist = [-1] * (n + 1)
    q = deque()
    
    dist[s] = 0
    q.append(s)
    
    while q:
        u = q.popleft()
        
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
                
    print(*dist[1:])

if __name__ == "__main__":
    main()

算法及复杂度

算法：广度优先搜索 (Breadth-First Search, BFS)
时间复杂度： $O(N+M)$ ，其中 $N$ 是顶点数， $M$ 是边数。因为每个顶点和每条边最多被访问一次。
空间复杂度： $O(N+M)$ ，主要用于存储邻接表。距离数组和队列的空间复杂度为 $O(N)$ 。