题解 | 【模板】单源最短路2

解题思路

1. 使用邻接表存储图
1. 使用 $\text{Dijkstra}$ (可见文末) 算法求解从 $1$ 号点到其他所有点的最短距离。
1. 检查是否能到达 $n$ 号点，如果不能到达则输出 $-1$ 。

代码

cpp
java
python

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

struct Edge {
    int v, w;
    Edge(int _v, int _w) : v(_v), w(_w) {}
};

vector<vector<Edge>> g;  // 邻接表
vector<int> dist;        // 存储最短距离
vector<bool> visited;    // 标记是否访问过

void dijkstra(int n, int start) {
    dist.assign(5001 + 1, INF);
    visited.assign(5001 + 1, false);
    dist[start] = 0;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        
        for (const Edge& e : g[u]) {
            int v = e.v, w = e.w;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    g.resize(5001 + 1);
    
    // 建图
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);  // 无向图需要加两条边
    }
    
    // 求最短路
    dijkstra(n, 1);
    
    // 输出结果
    cout << (dist[n] == INF ? -1 : dist[n]) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Edge {
        int v, w;
        Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
    
    static final int INF = 0x3f3f3f3f;
    static List<List<Edge>> g;
    static int[] dist;
    static boolean[] visited;
    
    static void dijkstra(int n, int start) {
        dist = new int[5001 + 1];
        visited = new boolean[5001 + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, start});
        
        while (!pq.isEmpty()) {
            int u = pq.poll()[1];
            
            if (visited[u]) continue;
            visited[u] = true;
            
            for (Edge e : g.get(u)) {
                int v = e.v, w = e.w;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        g = new ArrayList<>();
        for (int i = 0; i <= 5001; i++) {
            g.add(new ArrayList<>());
        }
        
        // 建图
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            g.get(u).add(new Edge(v, w));
            g.get(v).add(new Edge(u, w));
        }
        
        // 求最短路
        dijkstra(n, 1);
        
        // 输出结果
        System.out.println(dist[n] == INF ? -1 : dist[n]);
    }
}

from heapq import heappush, heappop
from collections import defaultdict
INF = float('inf')

def dijkstra(g, n, start):
    dist = [INF] * (5001 + 1)
    visited = [False] * (5001 + 1)
    dist[start] = 0
    
    pq = [(0, start)]
    
    while pq:
        d, u = heappop(pq)
        
        if visited[u]:
            continue
        visited[u] = True
        
        for v, w in g[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heappush(pq, (dist[v], v))
    
    return dist

def main():
    n, m = map(int, input().split())
    
    # 建图
    g = defaultdict(list)
    for _ in range(m):
        u, v, w = map(int, input().split())
        g[u].append((v, w))
        g[v].append((u, w))
    
    # 求最短路
    dist = dijkstra(g, n, 1)
    
    # 输出结果
    print(-1 if dist[n] == INF else dist[n])

if __name__ == "__main__":
    main()

算法及复杂度分析：

算法： $\text{Dijkstra}$ 算法
空间复杂度： $\mathcal{O}(N M)$ ，其中 $N$ 是节点数， $M$ 是边数
时间复杂度： $\mathcal{O}(M * \log N)$
- 使用优先队列的 $\text{Dijkstra}$ 算法，每条边最多被处理一次
- 每次从优先队列中取出和插入元素的时间复杂度是 $\mathcal{O}(\log N)$
- 总时间复杂度为 $\mathcal{O}(M * \log N)$

优化点：

1. 使用邻接表而不是邻接矩阵存储图，减少空间复杂度
1. 使用优先队列优化的 $\text{Dijkstra}$ 算法，而不是朴素 $\text{Dijkstra}$ 算法
1. 使用 $\text{visited}$ 数组避免重复访问节点

Dijkstra 算法基本概念

Dijkstra 算法是一种用于计算图中单源最短路径的算法，适用于边权为非负数的有向图或无向图。

算法核心思想

贪心策略：每次选择当前未访问的、距离源点最近的顶点
松弛操作：通过已知最短路径来更新其他顶点的最短路径估计值

算法步骤

初始化：

// 初始化距离数组和访问标记
vector<int> dist(n + 1, INF);  // 所有点到起点的距离初始化为无穷大
vector<bool> visited(n + 1, false);  // 标记数组初始化为未访问
dist[start] = 0;  // 起点到自身的距离为0

主循环：

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, start});  // 将起点加入优先队列

while (!pq.empty()) {
    int u = pq.top().second;  // 当前距离源点最近的顶点
    pq.pop();
    
    if (visited[u]) continue;  // 如果已经访问过，跳过
    visited[u] = true;  // 标记为已访问
    
    // 对所有相邻边进行松弛操作
    for (const Edge& e : g[u]) {
        int v = e.v, w = e.w;
        if (dist[u] + w < dist[v]) {  // 如果找到更短的路径
            dist[v] = dist[u] + w;  // 更新距离
            pq.push({dist[v], v});  // 加入优先队列
        }
    }
}

详细示例

考虑这个图：

     2
1 ------- 2
|         |
3         7
|         |
3 ------- 4
     5

让我们一步步执行算法（求 1 到 4 的最短路）：

// 初始状态：
dist = [0, INF, INF, INF]  // 1号点到各点的距离
visited = [false, false, false, false]
pq = [(0,1)]  // (距离,顶点)

// 第一步：处理1号点
访问1号点，更新邻居：
dist = [0, 2, 3, INF]
visited = [true, false, false, false]
pq = [(2,2), (3,3)]

// 第二步：处理2号点（距离最小）
访问2号点，更新邻居：
dist = [0, 2, 3, 9]  // 通过2到4的距离是9
visited = [true, true, false, false]
pq = [(3,3), (9,4)]

// 第三步：处理3号点
访问3号点，更新邻居：
dist = [0, 2, 3, 8]  // 通过3到4的距离是8
visited = [true, true, true, false]
pq = [(8,4)]

// 第四步：处理4号点
访问4号点，算法结束
最终结果：dist[4] = 8

代码实现（带注释版本）

struct Edge {
    int v, w;  // v是目标顶点，w是边权
    Edge(int _v, int _w) : v(_v), w(_w) {}
};

vector<vector<Edge>> g;  // 邻接表存储图
vector<int> dist;        // 存储最短距离
vector<bool> visited;    // 标记是否访问过

void dijkstra(int n, int start) {
    // 初始化
    dist.assign(n + 1, INF);
    visited.assign(n + 1, false);
    dist[start] = 0;
    
    // 优先队列，存储pair<距离, 顶点编号>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int u = pq.top().second;  // 取出当前最短距离的顶点
        pq.pop();
        
        if (visited[u]) continue;  // 如果已访问过，跳过
        visited[u] = true;  // 标记为已访问
        
        // 遍历所有出边
        for (const Edge& e : g[u]) {
            int v = e.v, w = e.w;
            // 松弛操作
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;  // 更新距离
                pq.push({dist[v], v});  // 加入优先队列
            }
        }
    }
}

算法特点

正确性保证：
- 基于贪心策略
- 每次选择的顶点的最短路径一定是正确的
时间复杂度：
- 优先队列版本： $\mathcal{O}(M * \log N)$
- 朴素版本： $\mathcal{O}(N^2)$
- $M$ 是边数， $N$ 是顶点数
适用条件：
- 边权必须为非负数
- 可以处理有向图和无向图
局限性：
- 不能处理负权边
- 不能检测负环

常见优化

双端队列优化：对于边权为0/1的图
堆优化：使用优先队列代替朴素算法
状态记录：记录路径信息

这就是 $\text{Dijkstra}$ 算法的核心内容。