上边n表示节点个数，m表示边，其中稠密图用邻接矩阵存，稀疏图用邻接表来存。
稀疏图与稠密图定义：数据结构中对于稀疏图的定义为：有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图（sparse graph），反之边的条数|E|接近|V|²，称为稠密图（dense graph）。（来自百度百科）
所有边权都是正数
Dijkstra算法
1.朴素Dijkstra算法
模板
s数组：标记当前已经确定最短距离的点
void Dijkstra()
{
dist[1] = 0, dist[i] = +$infty$ //初始化
for i: 0 ~ n //n个点
for j；1 ~ n
t <- 不在s中的，距离最近的点
st[t] = true; //标记
for j；1 ~ n
用t更新其他的点的距离
}
例题
给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出-1。
数据范围
1 ≤ n ≤ 500,
1 ≤ m ≤ 10^5,
图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
首先题目中说明存在重边和自环，我们用邻接矩阵来存图必须要解决这个问题，因此我们做这样的决策：对于重边，取最小；对于自环，忽略不计，设为0。
因此可以这样：1.将g数组全部初始化为0 2.g[a][b] = min(g[a][b], c)
根据上边稀疏图与稠密图定义可知：这是一个稠密图，因此用邻接矩阵来存图
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N]; //邻接矩阵存图
int dist[N]; //图中每个点到1的距离
bool st[N]; //表示某个点的最短距离是否被确定
int Dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n; i++) //确定n个点的最短距离 确定好每个点到起点的最短距离
{
int t = -1;
for(int j = 1; j <= n; j++) //寻找不在st中 距离最近的点
if(!st[j] && (t == -1 || dist[t] > dist[j])) //在还没有确定的点中找到距离1最近的点
t = j;
for(int j = 1; j <= n; j++) //用t更新其他点的距离
{
dist[j] = min(dist[j], dist[t] + g[t][j]); //用1~t+t~j的长度更新1~j的长度
}
st[t] = true; //表示已经t这个点已经确定最短距离
}
if(dist[n] == 0x3f3f3f3f) return -1; //表示1与n不连通
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c); //用邻接矩阵来存图
}
printf("%d
", Dijkstra());
return 0;
}
2.堆优化Dijkstra算法
看这个模板
s数组：标记当前已经确定最短距离的点
void Dijkstra()
{
dist[1] = 0, dist[i] = +$infty$ //初始化
for i: 0 ~ n //n个点
for j；1 ~ n
**t <- 不在s中的，距离最近的点
st[t] = true; //标记
for j；1 ~ n
用t更新其他的点的距离
}
其中加**的那一步，我们寻找最小点的过程遍历了所有的边，很费时间，所以我们可以直接用优先队列定义一个小根堆弹出距离1最小的节点（即堆顶）， 省略了查找的过程，更新后的节点则重新压入队列尾部。
堆优化后的Dijkstra代码：（相比于上题更改了数据范围，1 ≤ n,m ≤ 1.5×10^5 是一个稀疏图，因此用邻接表来存图）
int Dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; //创建小根堆
heap.push({0, 1}); //second是编号 first是距离 因为根据优先队列会先根据第一个关键字排序 因此这样设定
while(heap.size())
{
auto t = heap.top();
heap.pop();
int var = t.second; //记录编号
if(st[var]) continue; //如果已经确定距离 则continue
st[var] = true; //标记
for(int i = h[var]; i != -1; i = ne[i]) //遍历当前点的所有出边 因为是稀疏图用邻接表来存储
{
int j = e[i];
if(dist[j] > dist[var] + w[i]) //更新
{
dist[j] = dist[var] + w[i];
heap.push({dist[j], j});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1; //说明没被更新
return dist[n];
}
用邻接表存图不需要考虑重边和自环
总代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII; //first表示距离 second表示编号
const int N = 1e6+10;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; //稀疏图用邻接表来存
}
int Dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; //创建小根堆
heap.push({0, 1});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int var = t.second; //记录编号
if(st[var]) continue;
st[var] = true;
for(int i = h[var]; i != -1; i = ne[i]) //遍历当前点的所有出边
{
int j = e[i];
if(dist[j] > dist[var] + w[i]) //更新
{
dist[j] = dist[var] + w[i];
heap.push({dist[j], j});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
printf("%d
", Dijkstra());
return 0;
}
存在负权边
Bellman-Ford算法
处理存在有负权边求最短路的情况，但是如果存在负权回路则最短路就可能不存在，即-(infty)，因此求最短路一般都没有负权回路，但是也不排除有负权回路的情况，例如这种：
另外我们还可以求有边数限制的最短路，因为有边数限制，所以存在负权回路也没有关系。
例题：求有边数限制的最短路
给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数n，m，k。
接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。
如果不存在满足条件的路径，则输出“impossible”。
数据范围
1 ≤ n,k ≤ 500,
1 ≤ m ≤ 10000,
任意边长的绝对值不超过10000。
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3
因此这种题的模板：
backup数组使用来备份dist数组的
void Bellman_Ford()
{
for k次 //不超过k条边的最短距离
memcpy(backup, dist, sizeof dist); //备份 因为防止串联
for 所有边 a，b，w
dist[b] = min(dist[b], backup[a] + w);
}
上面的串联是因为可能出现这种情况：
这中情况下，如果我们限制边的条数为1，那么最短路就是3，而不是2，如果我们用dist[a] + w来更新dist，则会导致dist[3] = 2，即最短路距离为2，可与事实不符。
因此我们采用第k次遍历时dist的备份，用备份来更新dist。
从1->2->3:
备份：dist[1] = 0, dist[2] = +(infty), dist[3] = +(infty) (备份)
更新：dist[1] = 0, dist[2] = min(+(infty), +(infty)+1) = +(infty), dist[3] = min(+(infty), +(infty)+1), 这样以来dist[2]于dist[3]就不会被更新啦。
从1->3:
备份：dist[1] = 0, dist[3] = +(infty) (备份)
则：dist[3] = min(dist[3], dist[1] + 3) = 3
还有一个问题就是如何返回：
没有找到路径返回-1，如果这样写的话：if(dist[n] > 0x3f3f3f3f) return -1,那就错了，因为负权边的存在，有的点可能被更新了，小于0x3f3f3f3f，因此这样写就错了。
由此可见题目中数据范围因为500*10000，按极限最多500w，因此说最短路最多也就是0x3f3f3f3f-500w，不可能再大了，因此我们可以把条件设置成这样：if(dist[n] > 0x3f3f3f3f) return -1。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 512, M = 10010;
struct Edge
{
int a, b, w;
}edges[M];
int n, m, k;
int dist[N], backup[N];
int Bellman_Ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < k; i++) //最多经过k条边
{
memcpy(backup, dist, sizeof dist); //备份一下
for(int j = 0; j < m; j++) //一共m条边
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w); // 只用上一次迭代的结果来更新 这样就不会发生串联
}
}
if(dist[n] > 0x3f3f3f3f / 2) return -1; //由于存在负权边 因此在更新dist的时候可能会导致没有到过的点更新成小于0x3f3f3f3f
//因为数据是500*10000,最多五百万,因此最短路最多也得是0x3f3f3f3f-500w,不可能再大了，因此大于这个值说明一定不存在最短路
return dist[n];
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i = 0; i < m; i++)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}
int t = Bellman_Ford();
if(t == -1) puts("impossible");
else printf("%d
", dist[n]);
return 0;
}
spfa算法
这个算法优化了Bellman-ford算法，在更新的那一步，dist[b] = min(dist[b], backup[a] + w)，我们用一个for循环更新了所有的边，其实没有必要这样，我们只需要每次更新一个节点的出边即可，因此这里就可以用一个队列来优化，队列里边存的时待更新的点。
模板
void spfa()
{
queue <- 1
while 队列不空
1.t <- front, q.pop()
2.更新t的所有出边 t->b: queue <- b
}
例题 1：求最短路
给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出”impossible”。
数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过10000。
输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
2
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5+10;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; //稀疏图用邻接表来存
}
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true; //标记其在堆中
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false; //st数组的是否存在不影响程序的准确性 只通过节点是否重入队复影响程序的效率
for(int i = h[t]; i != -1; i = ne[i]) //遍历所有出边
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1; //因为这里用了队列到达不了的边是一定不会被更新的
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int t = spfa();
if(t == -1) puts("impossible");
else printf("%d
", t);
return 0;
}
例题 2：判断负环
抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理 。（来自百度百科）
我们用一个cnt数组来计数，每遍历到一个节点就+1，这里假设有n个节点，如果出现cnt[j] >= n，那么说明有环，根据抽屉原理，cnt[j] = 11，则必有两个点是重合的，那么说明就一定存在一个环。
给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
如果图中存在负权回路，则输出“Yes”，否则输出“No”。
数据范围
1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过10000。
输入样例：
3 3
1 2 -1
2 3 4
3 1 -4
输出样例：
Yes
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2010, M = 10010;
int h[N], e[M], ne[M], w[M], idx;
int n, m;
int dist[N], cnt[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa()
{
queue<int> q;
for(int i = 1; i <= n; i++) //所有点入栈 因为环不一定从1开始
{
q.push(i);
st[i] = true;
}
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i]) //因为如果存在负环则某点距离一定是负无穷 所以这里一定会被更新的
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true; //说明出现负环
if(!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
return false;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if(spfa()) puts("Yes");
else puts("No");
return 0;
}
Floyd算法
用来求多元最短路，即任意两个点的最短路经。
据说这是求最短路最简单的算法，基于动态规划，原理我还不是很明白，因此只能等学完动态规划后再回来看吧。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N];
void floyd() //模板
{
for(int k = 1; k <= n; k++)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
int main()
{
cin >> n >> m >> Q;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i == j) d[i][j] = 0; //如果存在自环 则设为无边
else d[i][j] = INF;
}
}
while(m--)
{
int a, b, c;
cin >> a >> b >> c;
d[a][b] = min(d[a][b], c); //如果存在重边 取最短边
}
floyd();
while(Q--)
{
int a, b;
cin >> a >> b;
int t = d[a][b];
if(t > INF / 2) puts("impossible");
else cout << t << endl;
}
return 0;
}