最短路径算法讲解（以 Dijkstra 为主）

一、引言：为什么需要最短路径？

在现实生活中，我们常常遇到这样的问题：

地图导航软件如何计算从A地到B地的最短路线？
网络通信中，数据包如何选择最优路径传输？
游戏中角色如何自动寻路？

这些问题都可以抽象为图论中的最短路径问题。

本讲义将围绕Dijkstra算法展开，适合已经掌握**深度优先搜索（DFS）和动态规划（DP）**基础的同学。我们将从图的基本概念讲起，逐步过渡到 Dijkstra 的原理、实现与优化，并提供配套 C++ 示例代码与练习题。

二、图的基本概念回顾

1. 图的定义

图由顶点（节点）和边组成：

无向图：边没有方向
有向图：边有方向
带权图：每条边有权值（如距离、时间等）

2. 图的表示方法

邻接矩阵：适用于稠密图
邻接表：适用于稀疏图，常用方式

// 邻接表示例（C++）
#include <vector>
#include <utility> // for pair

using namespace std;

const int MAXN = 100010;
vector<pair<int, int>> graph[MAXN];  // 存储 (终点, 权重)

三、最短路径问题分类

类型	描述	常用算法
单源最短路径	给定一个起点，求它到所有其他点的最短路径	Dijkstra、Bellman-Ford
多源最短路径	求任意两点之间的最短路径	Floyd-Warshall

本讲义重点讲解单源最短路径问题中的经典算法——Dijkstra算法。

四、Dijkstra 算法详解

1. 适用范围

图中不能有负权边
可用于有向图或无向图
权值必须非负

2. 核心思想

Dijkstra 是一种贪心策略 + 广度优先搜索的变体：

维护一个已确定最短路径的集合 S
每次从未确定的点中选择离起点最近的点 u 加入 S
用 u 更新其邻居的最短路径估计值

五、Dijkstra 算法实现（C++）

1. 使用堆优化的版本（推荐）

使用 priority_queue 实现最小堆，提升效率。

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 100010;
const int INF = 0x3f3f3f3f;

vector<pii> graph[MAXN];   // graph[u] 存储的是 (v, w)
int dist[MAXN];
bool visited[MAXN];

int n, m;  // n个节点，m条边

void dijkstra(int start) {
    memset(dist, INF, sizeof(dist));
    dist[start] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) continue;

        for (auto edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;

            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

2. 示例图

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        // 若是无向图，再加一句：
        // graph[v].push_back({u, w});
    }

    dijkstra(1);  // 假设起点是节点1

    for (int i = 1; i <= n; ++i) {
        cout << "Distance from 1 to " << i << ": ";
        if (dist[i] == INF)
            cout << "INF" << endl;
        else
            cout << dist[i] << endl;
    }

    return 0;
}

六、进阶内容

1. 打印路径

我们可以记录前驱节点来还原路径：

int prev[MAXN];  // 记录前驱节点

void dijkstra_with_path(int start) {
    memset(dist, INF, sizeof(dist));
    memset(prev, -1, sizeof(prev));
    dist[start] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) continue;

        for (auto edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;

            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                prev[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
}

void print_path(int end) {
    if (prev[end] == -1 && end != 1) {
        cout << "No path!" << endl;
        return;
    }

    vector<int> path;
    for (int v = end; v != -1; v = prev[v])
        path.push_back(v);

    reverse(path.begin(), path.end());
    for (int node : path)
        cout << node << " ";
    cout << endl;
}

七、Dijkstra 与其他算法对比

算法	是否支持负权边	时间复杂度	适用场景
Dijkstra	❌（不支持）	O((V+E)logV)	非负权图
Bellman-Ford	✅（支持）	O(VE)	边数少的小图
SPFA	✅（平均快）	O(kE)，k一般为2~3	实际应用较多
Floyd-Warshall	✅	O(V³)	多源最短路径

八、典型应用场景举例

地图导航系统（如百度地图、高德地图）
网络路由协议（如 OSPF）
游戏 AI 寻路算法（A* 算法是 Dijkstra 的启发式改进）

九、练习题推荐（C++ 版）

洛谷 P3371 【模板】单源最短路径（弱化版）
- 标准 Dijkstra 模板题
LeetCode 743. Network Delay Time
- 有向图中最大到达时间

🟡 中等题

AcWing 850. Dijkstra求最短路 II
- 稠密图，建议练习邻接矩阵写法
LeetCode 1631. Path With Minimum Effort
- 最小代价路径，需修改松弛条件

🔴 提高题

LeetCode 1514. Path with Maximum Probability
- 改造版 Dijkstra（最大概率路径）
洛谷 P4779 【模板】单源最短路径（标准版）

🟢 简单题

堆优化 Dijkstra 模板题（推荐用 pair 和 priority_queue）

十、总结与建议

学习路线图：

图的基本概念 → BFS/DFS → 动态规划 → 最短路径问题 → Dijkstra → 扩展变形

*学习笔记

暂没有学习笔记，快来抢first blood ！

一、引言：为什么需要最短路径？​

二、图的基本概念回顾​

1. 图的定义​

2. 图的表示方法​

三、最短路径问题分类​

四、Dijkstra 算法详解​

1. 适用范围​

2. 核心思想​

五、Dijkstra 算法实现（C++）​

1. 使用堆优化的版本（推荐）​

2. 示例图​

六、进阶内容​

1. 打印路径​

七、Dijkstra 与其他算法对比​

八、典型应用场景举例​

九、练习题推荐（C++ 版）​

🟡 中等题​

🔴 提高题​

🟢 简单题​

十、总结与建议​

学习路线图：​

推荐学习顺序：​

*学习笔记​