解题思路

无向图最短路径解题思路（BFS）

1. 问题分析

  • 无向图中找最短路径
  • 边的权重都是
  • 需要处理不连通的情况
  • 使用 （广度优先搜索）最适合解决这类问题

2. 解题步骤

  1. 图的存储

    • 使用邻接表存储图
    • 每个节点存储其相邻节点的列表
    • 因为是无向图，每条边需要存两次

  2. BFS实现

    • 使用队列存储待访问的节点
    • 使用数组记录到每个点的距离
    • 使用 数组标记已访问的点

  3. 具体流程

    • 从 号点开始
    • 将 号点加入队列，距离设为
    • 每次取出队首节点，遍历其相邻节点
    • 对未访问的相邻节点，更新距离并加入队列

  4. 结果判断

    • 如果能访问到 号点，输出距离
    • 如果不能访问到 号点，输出

3. 注意事项

  1. 初始化：
    • 距离数组初始化为
    • 号点的距离初始化为
  2. 边界处理：
    • 检查图是否为空
    • 处理孤立点的情况

这种方法适合解决无权图（或权值相等）的最短路径问题，实现简单且效率高。

代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int shortestPath(int n, int m, vector<vector<int>>& edges) {
        // 建图
        vector<vector<int>> graph(5000 + 1);
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        
        // BFS
        vector<int> dist(5000 + 1, -1);  // 距离数组初始化为-1
        queue<int> q;
        q.push(1);
        dist[1] = 0;
        
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            
            for (int next : graph[cur]) {
                if (dist[next] == -1) {  // 未访问过
                    dist[next] = dist[cur] + 1;
                    q.push(next);
                }
            }
        }
        
        return dist[n];  // 如果不可达，dist[n]就是-1
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> edges;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back({u, v});
    }
    
    Solution sol;
    cout << sol.shortestPath(n, m, edges) << endl;
    
    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();
        
        // 建图
        List<List<Integer>> graph = new ArrayList<>(5000 + 1);
        for (int i = 0; i <= 5000; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 读入边
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        // BFS
        int[] dist = new int[5000 + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        dist[1] = 0;
        
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            
            for (int next : graph.get(cur)) {
                if (dist[next] == -1) {
                    dist[next] = dist[cur] + 1;
                    queue.offer(next);
                }
            }
        }
        
        System.out.println(dist[n]);
    }
}

from collections import defaultdict, deque

class Solution:
    def shortestPath(self, n: int, m: int, edges: list) -> int:
        # 建图
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
            
        # BFS
        dist = [-1] * (5000 + 1)  # 距离数组初始化为-1
        q = deque([1])
        dist[1] = 0
        
        while q:
            cur = q.popleft()
            
            for next_node in graph[cur]:
                if dist[next_node] == -1:  # 未访问过
                    dist[next_node] = dist[cur] + 1
                    q.append(next_node)
                    
        return dist[n]

def main():
    n, m = map(int, input().split())
    edges = []
    for _ in range(m):
        u, v = map(int, input().split())
        edges.append([u, v])
        
    sol = Solution()
    print(sol.shortestPath(n, m, edges))

if __name__ == "__main__":
    main()

算法及复杂度分析

  • 算法：无向图最短路径，BFS
  • 时间复杂度：
    • 是节点数
    • 是边数
  • 空间复杂度：
    • 需要距离数组和访问数组