概念
单源最短路径，顾名思义，就是只有一个起点，并且到其他的点都是最短的。
树有无环、联通的特点，所以任意两点间简单路径唯一，以起点作为根节点 \(DFS/BFS\) 求距离即可。
之前在图上跑最短路都是用 \(bfs\)，但他只能处理边权相同的图，所以，今天的最短路是可以处理其他边权的。
著名的单源最短路径算法有 Dijkstra，Bellman-Ford，SPFA等算法。
dijkstra 算法
dijkstra 是一种点核心的单源最短路算法，核心思想是：
- 找到没有确定最短路的点里面，距离起点最近的点u。
- 用起点到点u的距离dis[u]，尝试更新u的邻接点的最短距离。
重复以上操作直到所有点的最短距离都被确定。
代码：
#include <bits/stdc++.h>using namespace std;
#define ll long long
const int MAXH = 1e5 + 7;
const int INF = 0x3f3f3f3f;
int n,m,s;
struct edge{int v,w;
};
vector<edge>e[MAXH];
struct node{int dis,u;bool operator > (const node &x) const{return dis > x.dis;}
};
int dis[MAXH];
bool vis[MAXH];
priority_queue<node,vector<node>,greater<node>>q;
inline void dijkstra(int sx){memset(dis,0x3f,sizeof(dis));memset(vis,false,sizeof(vis));while(!q.empty()) q.pop();q.push((node){0,sx});dis[sx] = 0;while(!q.empty()){int u = q.top().u;q.pop();if(vis[u])continue;vis[u] = 1;for(auto ed : e[u]){int v = ed.v,w = ed.w;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.push((node){dis[v],v});}}}
}
int main(){scanf("%d%d%d",&n,&m,&s);for(int i = 1;i <= m;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);e[x].push_back((edge){y,w});}dijkstra(s);for(int i = 1;i <= n;i++)printf("%d ",dis[i]);return 0;
}
bellman-ford 算法
bellman算法是一种边核心的最短路算法。
松弛操作与 dijkstra 中相同，假设有一条从u到v，边权为w的边，那么我们就可以尝试用 dis[u] + w 来更新 dis[v]。
在每一轮循环中，我们尝试用每一条边更新这条边的终点的最短路，复杂度 \(O(m)\)。
如果起点不能到达负环，存在最短路，那么最短路最多包括 n-1 条边，
每轮松弛都会使最短路至少多一条边。
所以最多需要进行n-1轮循环，最终复杂 \(O(nm)\)
SPFA 算法
SPFA，是 bellman-ford 的队列优化。
只有上一次被松弛过的终点，才有作为起点松弛的价值。
所以可以用一个队列存被松弛过的终点的集合，每次取出队头松弛该点的出边。
在随机图和一些有特殊性质的图上表现优秀，
但复杂度上界和bellman相同，也是 \(O(nm)\)。
所以，没负权边还是用 dijkstra 把。
下次再也不用spfa跑正权边了，被卡了！！！！