1. Floyd算法：O(|V|³)，多源最短路，适用于出现负边权的情况，但无法处理存在负权回路的情况。
2. Dijkstra算法：O(|V|²)，单源最短路，不能处理存在负边权的情况。（边比较多时用）
3. Bellman-Ford算法：O(|V||E|)，单源最短路，适用于出现负边权的情况，但无法处理存在负权回路的情况。（边比较少时用）
v是点数，E是边数
多源最短路：计算每一对顶点的最短路径
单源最短路：计算从1个起点到途中所有其他顶点的最短路径
本期来优化后面两个算法
Dijkstra算法：
未优化：
#include <iostream>
#include <vector>
#include <utility>
#define inf 1001
using namespace std;
int n, m, cnt; // n<100 0<权值<1000
int h[105];
struct Edge
{
int to, w, next;
} e[10005];
int dis[105], v[105];
void add(int u, int v, int w)
{
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = h[u];//下一条边
h[u] = cnt;
cnt++;
}
void dij(int x)
{
for (int j = 1; j <= n; j++)
dis[j] = inf;//dis数组实时记录并更新从起点 x 到图中每一个节点的当前最短距离估计值。
dis[x] = 0;
for (int i = 1; i <= n; i++)
v[i] = 0;
for (int i = 1; i <= n; i++)//遍历所有点
{
int minn = inf, k = -1;
for (int j = 1; j <= n; j++)//从1-n中找到x， minn = 0，并把 k 设为起点 x 的编号，这是第一次，后面 就是找出来一个最短路径的节点
{
if (v[j] == 0 && dis[j] < minn)
{
minn = dis[j];
k = j;
}
}
if (k == -1) break;//如果找不到任何一个处理，后面也不用看了
v[k] = 1;
for (int i = h[k]; i != -1; i = e[i].next)//不断遍历下一条边
{
int u = e[i].to;//下一条边终点的值
if (v[u] == 0 && dis[u] > dis[k] + e[i].w)
dis[u] = dis[k] + e[i].w;
}
}
}
int main()
{
memset(h, -1, sizeof(h));
cin >> n >> m;
int x, y, w;
for (int i = 1; i <= m; i++)
{
cin >> x >> y >> w; // x—->y
add(x, y, w);
}
cin >> x;
dij(x);
for (int i = 1; i <= n; i++)
{
cout << dis[i] << " ";
}
cout << endl;
return 0;
}
/*
输出样例
5 5
2 3 2
1 2 3
*/
优化：
使用小根堆，也就是优先队列，遵循（谁的优先级最高，谁就先出去）
#include <iostream>
#include <vector>
#include <utility>
#include <queue> // 引入优先队列头文件
#define inf 1001
using namespace std;
int n, m, cnt;
int h[105];
struct Edge {
int to, w, next;
} e[10005];
int dis[105], v[105]; // v数组依然需要，用于标记节点是否已确定
// <1> 定义优先队列的结构
// pair的第一个元素是距离，第二个是节点编号
// greater<> 表示距离小的优先级高（小根堆）
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
void add(int u, int v, int w) {
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = h[u];
h[u] = cnt;
cnt++;
}
void dij(int x) {
// <2> 初始化
for (int j = 1; j <= n; j++)
dis[j] = inf;
dis[x] = 0;
// <3> 将起点{距离, 编号}放入队列
pq.push({0, x});
while (!pq.empty()) { // <4> 队列不为空就继续
// <5> 取出队首（当前距离最小的）
int d = pq.top().first; // 当前取出的距离
int k = pq.top().second; // 当前取出的节点
pq.pop();
// <6> 惰性删除：如果这个节点已经被处理过，或者距离变大了，就跳过
if (v[k] == 1 || d > dis[k])
continue;
// <7> 标记节点k已确定，进行松弛操作
v[k] = 1;
for (int i = h[k]; i != -1; i = e[i].next) {
int u = e[i].to;
// <8> 如果通过k到u更近，就更新
if (dis[u] > dis[k] + e[i].w) {
dis[u] = dis[k] + e[i].w;
// <9> 把更新后的新距离和节点放入队列
pq.push({dis[u], u});
}
}
}
}
int main() {
memset(h, -1, sizeof(h));
cin >> n >> m;
int x, y, w;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> w;
add(x, y, w);
}
cin >> x;
dij(x);
for (int i = 1; i <= n; i++) {
cout << dis[i] << " ";
}
cout << endl;
return 0;
}
优化后时间复杂度O（(|V|+|E|)*log|V|)
Bellman-Ford算法：
补充：第i轮一定有机会被更新的点是上一轮被更新的点的邻接点
优化：
可以发现，每一轮遍历dis值减小的点，是上一轮dis值减小的点的邻接点。
所以每一轮没必要遍历所有的边了，只遍历上一轮dis值减小的点的出边即可，即只找上一轮dis值减小的点的邻接点。则，采用队列进行优化，将dis值减小的点入队，每次只找队列中点的邻接点进行更新。
——-SPFA算法
使用该优化后就可以判断带环负权图
一个点最多入队不到n次，因为入队的都是指向的那个点，最多有n-2个点（还有个起点不算）指向它
这里的队列就用普通的就行，不用优先队列
示例：
bool spfa(int x)
{
for(int i=1; i<=n; i++)
dis[i]=inf;
queue<int> q;
int u, k;
dis[x]=0;
v[x]=1;
q.push(x);
while(!q.empty())
{
u=q.front();
q.pop();
v[u]=0; // u不在队列中了
for(int i=h[u]; i!=-1; i=e[i].next)
{
k=e[i].to;
if(dis[k]>dis[u]+e[i].w)
{
dis[k]=dis[u]+e[i].w; // k点被更新
cur[k]=cur[u]+1; // 记录起点到k的边数
if(cur[k]>=n-1) return 0;
if(v[k]==0)
{
q.push(k);
v[k]=1;
}
}
}
}
}
