NC158 单源最短路
单源最短路是图论算法里非常重要的基础算法，似乎没有之一。。。。。。
常用的算法有dijkstra算法和SPFA算法，下面分别介绍。
题意
给你一个有向图，n点m边，有重边无自环，权值为正，求 1 到 n 的最短路，如果不存在，输出-1.
1. 迪杰斯特拉
这个似乎是数据结构课的新人杀手了。。。。
dijkstra算法的流程如下：
- 初始化dist[1]=0,其他为inf，令s集合表示已经确定最短距离的点
- 遍历n次：
- 寻找不在s中的，距离s集合最近的点t
vis[t]=true, 即加入s中- 遍历s中的所有点，对每个点j更新
dist[j]=min(dist[j],dist[t]+f[t][j])，实际这一步可以遍历全部点，因为dij算法不支持负边，无穷大加正数还是无穷大。
这样做，时间复杂度会达到，因为有两重的遍历，通常的题目是稀疏图（例如边数1e6），且点数达到1e5，肯定是不行的。
上述过程中的第3步，我们发现，加入t之后，用t更新s中的所有点是一个线性遍历的过程，但是，我们可以不用线性扫点，而是直接挑选距离S最近的点进行更新，所以可以维护一个小根堆，每次从堆顶取的就是不在S中距离起点最近的那个。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int 顶点数
* @param m int 边数
* @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
* @return int
*/
using pii = pair<int, int>;
// 定义小根堆，存储当前距离1号点的距离和下标
// 默认的priority_queue是大根堆，要特殊定义一下，这样写是固定写法。
// stl中，pair的比较是先比第一个，再比第二个，所以距离要放前面
using minheap = priority_queue<pii,vector<pii>,greater<pii> >;
static const int N = 210, M = 510; // 本题大约的数据范围是200个点，500个边。
// 定义初始距离为无穷大, 这个数约为1e9，够大，且相加不爆int，相乘不爆ll，是算法题中常见的无穷大定义
static const int INF = 0x3f3f3f3f;
// 前向星存储
struct Edge {
int to, next, dis;
} e[M];
int head[N], dist[N], idx = 1;
bool vis[N];
void add(int a, int b, int c) {
e[idx].to = b;
e[idx].next = head[a];
e[idx].dis = c;
head[a] = idx++;
}
void dijkstra(int start) {
memset(dist, 0x3f, sizeof dist);
dist[start] = 0;
minheap h;
h.push({0, start}); //先把起点放进去
while (!h.empty()) {
// 找到不在S中，距离起点最近的那个
int u = h.top().second;
h.pop();
if (!vis[u]) {
// 加入S中
vis[u] = true;
// 遍历出边
for (int i = head[u]; ~i; i = e[i].next) {
int j = e[i].to;
// 如果可以更新，就放进小根堆
if (dist[j] > dist[u] + e[i].dis) {
dist[j] = dist[u] + e[i].dis;
h.push({dist[j], j});
}
}
}
}
}
int findShortestPath(int n, int m, vector<vector<int> >& graph) {
memset(head, -1, sizeof head);
memset(vis, 0, sizeof vis);
for (auto g : graph) {
add(g[0], g[1], g[2]);
}
dijkstra(1);
if (dist[n] == INF) return -1;
return dist[n];
}
};- 时间复杂度：
, 宽搜部分按边遍历，堆中存的是点，入堆过程的复杂度是
.
- 空间复杂度：
. 堆中最多存了整个图的全部点。
2. spfa
方法一虽然经典，但是不支持负权边。下面介绍一种支持负权边的算法————SPFA(Shortest Path Faster Algorithm)算法。
算法流程如下：
- 维护一个队列，初始时加入起点
- 每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断dist[v]+len是否小于dist[u]，若小于则缩小dist[u]（这个操作叫松弛）
- 如果u没有访问过，则u入队
- 直到队列为空。
以样例为例，图解算法流程如下：
- 初始状态队列中为1，dist[i]=0, 其他为inf
- 1出队，2，4入队，更新dist[2]=2, dist[4]=5
- 2，4出队，3，5入队，更新dist[3]=5, dist[5]=10
- 3出队，更新dist[5]=9
- 5出队，队列为空
class Solution {
public:
static const int N = 210, M = 510; // 本题大约的数据范围是200个点，500个边。
static const int INF = 0x3f3f3f3f; // 定义初始距离为无穷大
struct Edge {
int to, next, dis; // 存储图
} e[M];
int head[N], dist[N], idx = 1;
bool vis[N];
void add(int a, int b, int c) {
e[idx].to = b;
e[idx].next = head[a];
e[idx].dis = c;
head[a] = idx++;
}
void spfa(int start) {
memset(dist, 0x3f, sizeof dist);
dist[start] = 0;
queue<int> q;
q.push(start);
vis[start] = true; //判重数组， 队列中有重复的点没有意义
while (q.size()) {
int t = q.front();
q.pop();
vis[t] = false;
// 遍历队头的点t的所有出边
for (int i = head[t]; ~i; i = e[i].next) {
int j = e[i].to; // t->j的有向边
// 松弛操作j点
if (dist[j] > dist[t] + e[i].dis) {
dist[j] = dist[t] + e[i].dis;
// 如果j没入队过，把j加入队列
if (!vis[j]) {
q.push(j);
vis[j] = true;
}
}
}
}
}
int findShortestPath(int n, int m, vector<vector<int> >& graph) {
memset(head, -1, sizeof head);
memset(vis, 0, sizeof vis);
// 邻接矩阵转换成链表形式存图
for (auto g : graph) {
add(g[0], g[1], g[2]);
}
spfa(1);
if (dist[n] == INF) return -1; // 如果没有更新到n点，说明不存在最短路径
return dist[n];
}
};- 时间复杂度：通常认为是
, m是边数，k是较大的常数，在特殊的数据下，最坏为
, 其中n是点数。
- 空间复杂度：
3. 总结
选择算法时，需要注意：
- 如果有负权边，必须使用spfa
- 如果没有负权边，对稀疏图建议使用前向星存储+堆优化dijkstra，对稠密图（边数是点数平方级别）的话，如果用堆优化版本，时间复杂度就变成了
, 反而劣于普通dij。因此稠密图建议用邻接矩阵存储的dij。当然，用spfa也可以，但记住这玩意在笔试中，如果题目条件给出边权为正，很可能会被出题人故意构造数据卡掉！
- 如果有负环，则最短路是负无穷大，判断方法是在spfa里增加一个数组记录下每个点的最短路被更新过几次，如果超过了n次，说明走到这个点的路径长度超过n了，这就证明在转圈，所以存在负环。
京公网安备 11010502036488号