嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！
我的博客：yuanManGan
什么是单源最短路？假设一个图中的两个顶点vi，vj，从vi到vj路径上所经过的权值之后就称为带权路径长度。
但vi到vj的路径有很多条，将带权路径长度最短的那条路径就称为最短路径。
• 单源最短路，即图中一个顶点到其它各顶点的最短路径。
• 多源最短路，即图中每对顶点间的最短路
我们先来讲解第一个解决方法：dijkstra 算法
该算法只能解决非负权图的单源最短路的问题
算法思想：贪心
每次拿出还未确定最短路径的点中，距离起点最近的点。
我们用dist数组来存储我们最终的结果，用edges来存储图的结构，用bool类型的st数组来标记已经找出有最短路径的顶点，我们可以将dist数组初始化为正无穷表示还未找到其最小路径，dist[1] = 0，表示1顶点是起点。
具体流程，拿出dist不等于∞的顶点指向的下一个顶点中最小权值的顶点(如果相同随便拿一个)，更新dist数组，将拿出的顶点和起点视为一个顶点，比较权值更新所有拿出的顶点的边的权值，重复操作。
模板题目：
【模板】单源最短路问题（弱化版）
题目来源： 洛谷
题目链接： P3371 【模板】单源最短路径（弱化版）
难度系数： ★★
常规版 dijkstra 算法：
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int, int>PII;
const int N = 1e4 + 10, INF = 2147483647;
int dist[N];
bool st[N];
vector<PII>edges[N];
int n, m, s;
void dijkstra()
{
for (int i = 0; i <= n; i++) dist[i] = INF;
dist[s] = 0;
//循环n次找n个顶点的边权情况
for (int i = 1; i < n; i++)
{
//找最小边权
int u = 0;
for (int j = 1; j <= n; j++)
if (!st[j] && dist[j] < dist[u]) u = j;
//打上标记然后松弛
st[u] = true;
for (auto &t : edges[u])
{
int v = t.first, w = t.second;
if (dist[v] > dist[u] + w)
dist[v] = dist[u] + w;
}
}
for (int i = 1; i <= n; i++) cout << dist[i] << " ";
}
int main()
{
cin >> n >> m >> s;
for (int i = 1; i <= m; i++)
{
int x, y, z; cin >> x >> y >> z;
edges[x].push_back({ y, z });
}
dijkstra();
return 0;
}
时间复杂度为O(n^2)
我们每次都要找出最小的元素，我们可以建一个小根堆来优化一下时间复杂度
堆优化版 dijkstra 算法
在常规版的基础上，⽤优先级队列去维护待确定最短路的结点,因为我们每次都得去找最小的边权，我们不如创建个小根堆，让搜索的时间复杂度为O(n*lg n)
它可以过这个要求时间复杂度更小的样例
【模板】单源最短路问题（标准版）
题⽬来源： 洛⾕
难度系数： ★★
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
//创建小根堆
priority_queue<PII, vector<PII>, greater<PII>> heap;
vector<PII> edges[N];
int n, m, s;
int dist[N];
bool st[N];
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
heap.push({ 0, s });//权值，顶点
while (heap.size())
{
auto t = heap.top();
heap.pop();
int v = t.second;
if (st[v]) continue;
st[v] = true;
for (auto& x : edges[v])
{
int u = x.first, w = x.second;
if (dist[u] > dist[v] + w)
{
dist[u] = dist[v] + w;
heap.push({ dist[u], u });
}
}
}
for (int i = 1; i <= n; i++) cout << dist[i] << " ";
}
int main()
{
cin >> n >> m >> s;
for (int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
edges[x].push_back({ y, z });
}
dijkstra();
return 0;
}但我们的dijkstra算法遇到了负边权时：
这时我们得采用其他算法了。
bellman-ford 算法
dijkstra算法以点出发，而这个bf算法则以边出发,这个算法可以解决边权为负数的情况。
算法核⼼思想：不断尝试对图上每⼀条边进⾏松弛，直到所有的点都⽆法松弛为⽌。
这个依然只能过第一个题目。
代码展示：
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10, INF = 2147483647;
vector<PII> edges[N];
int dist[N];
int n, m, s;
void bf()
{
for (int i = 0; i <= n; i++) dist[i] = INF;
dist[s] = 0;
// 最多进行 n - 1 次松弛操作
for (int i = 1; i < n; i++)
{
// 每一轮开始时将 flag 初始化为 false
bool flag = false;
for (int j = 1; j <= n; j++)
{
int u = j;
for (auto& t : edges[u])
{
int v = t.first, w = t.second;
if (dist[u] == INF) continue;
if (dist[u] + w < dist[v])
{
dist[v] = dist[u] + w;
flag = true;
}
}
}
// 每一轮结束后判断是否有边被松弛，若没有则提前结束
if (!flag) break;
}
for (int i = 1; i <= n; i++) cout << dist[i] << " ";
}
int main()
{
cin >> n >> m >> s;
for (int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
edges[x].push_back({ y, z });
}
bf();
return 0;
}spfa 算法
该算法依旧是对bf算法的优化，这里使用队列对bf算法进行优化。
在bf算法中很多时候我们不需要进行那么多的无用的松弛操作：
1.只有上一次被松弛的节点，它的出边，才可能引起下一次的松弛操作；
2.因此，如果用队列来维护"那些节点可能会引起松弛操作"，就能只访问必要的边了，降低了时间复杂度
虽然在⼤多数情况下 spfa 跑得很快，但其最坏情况下的时间复杂度为 。将其卡到这个复杂度
也是不难的，所以在没有负权边时最好使⽤ Dijkstra 算法。
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int>PII;
const int N = 1e4 + 10, INF = 2147483647;
vector<PII>edges[N];
int dist[N];
bool st[N];
queue<int> q;
int n, m, s;
void spfa()
{
for (int i = 0; i <= n; i++) dist[i] = INF;
dist[s] = 0;
q.push(s);
st[s] = true;
while (q.size())
{
auto u = q.front(); q.pop();
st[u] = false;
for (auto& t : edges[u])
{
int v = t.first, w = t.second;
if (dist[u] == INF) continue;
if (dist[u] + w < dist[v])
{
dist[v] = dist[u] + w;
if (!st[v])
{
q.push(v);
st[v] = true;
}
}
}
}
for (int i = 1; i <= n; i++) cout << dist[i] << " ";
}
int main()
{
cin >> n >> m >> s;
for (int i = 1; i <= m; i++)
{
int x, y, z; cin >> x >> y >> z;
edges[x].push_back({ y, z });
}
spfa();
return 0;
}