dijkstra算法
用于解决无负权边的单源最短路问题
朴素版：时间复杂度O(n^2)，适用于稠密图，优点比较好写，缺点n较大时会T，我们使用邻接矩阵来存图，用g[x][y]记录从x到y的边权，用dis[x]代表从源点到x的最短路，核心在于贪心策略，找源点出发所有边权的最小值，那么可证得此点的最短路一定为该边权值，那么将该点标记，再以此点作为源点，一直找寻更新下去，直到全部点都被标记为止，模板：
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
int n,m;
int g[N][N],dis[N],mk[N];
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1] = 0;
for(int i = 1;i <= n;i++){
int mx = 0x3f3f3f3f,idx;
for(int j = 1;j <= n;j++){
if(!mk[j]&&dis[j] < mx){
mx = dis[j];
idx = j;
}
}
mk[idx] = 1;
for(int j = 1;j <= n;j++) if(dis[j] > dis[idx]+g[idx][j]) dis[j] = dis[idx] + g[j][idx];
}
return;
}
int main(){
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof(g));
for(int i = 1;i <= m;i++){
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
g[x][y] = g[y][x] = min(g[x][y],v);
}
dijkstra();
if(dis[n] >= 0x3f3f3f3f) printf("-1");
else printf("%d",dis[n]);
return 0;
}
堆优化版：我们会发现朴素版在n较大的情况下数组内存和时间复杂度都会极大，那么就需要进行优化，我们发现找寻从源点出发的边权最大值的时间复杂度为n，这显然是不优的，这时候我们想到可以用优先队列（堆）——priority_queue将此过程优化为logn，而我们又发现此时仅优化这一过程是用处不大的，因为在比对过程中它的时间复杂度仍然为n，那么怎么办呢？我们联想到之前学过的链表，所以使用邻接表来储存双点间的最短路，那么此时查询的时间复杂度就变为了理想状态下O(m/n)，这个值一般是不大的，近似于log级别，更好的情况下近似于O(1)，此时外层循环枚举的是队列元素，最多有m个，所以我们整体的时间复杂度就优化为了O(mlogn)，这个就很万能了，但是受限于dijkstra算法策略的缺点，它仍不能解决边权为负值的情况，模板：
#include<bits/stdc++.h>
using namespace std;
const int N = 1000005,M = 5000005;//数组要开大一些，不然会T，why？
int n,m;
int hd[N],ver[M],nxt[M],val[M],dis[N],mk[N];
int idx,s;
struct node{
int idx,v;
};
priority_queue <node> q;
bool operator < (const node &x,const node &y){//重载运算符，用于排序结构体时的优先队列
return x.v > y.v;
}
void add(int x,int y,int v){
ver[++idx] = y;
val[idx] = v;
nxt[idx] = hd[x];
hd[x] = idx;
}
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1] = 0;
q.push((node){1,0});
while(q.size()){
node t = q.top();
q.pop();
if(mk[t.idx]) continue;
mk[t.idx] = 1;
for(int i = hd[t.idx];i;i = nxt[i]){
int y = ver[i];
if(!mk[y]&&dis[y] > dis[t.idx]+val[i]){
dis[y] = dis[t.idx]+val[i];
q.push((node){y,dis[y]});
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++){
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
if(x == y) continue;
add(x,y,v);
add(y,x,v);
}
s = 1;
dijkstra();
printf("%d",dis[n]);
return 0;
}
SPFA算法
可用于解决几乎所有单源最短路，尤其是边权有负值时
此算法的理论依据是三角不等式（czls所言），也就是当dis[i][l]+dis[k][j] > dis[i][j]时，我们将其更新为较小值，二维数组肯定是会炸空间的，所以我们也用邻接表来储存边，不过经过一些推导我们很快就发现，在一次暴力遍历（枚举全部边）中，我们最多只能确保1个点被更新为了全局最值，那这就很麻烦了，时间复杂度直接变为了O(mn)，怎么省略掉那些无意义的枚举呢？我们联系上述的dijkstra算法的思想，每次当我们找到并更新一个点的最小值时，只有它的邻点可能会被更新，所以我们以此点为中心扩散枚举它的所有邻点，用队列来实现这个效果，每次找到更小值时我们将它的所有邻点存在队列里（类似于广搜），时间复杂度在O(m)：链 到O(mn)：菊花图或者网格图 之间，相较于dijkstra它的优势在于可以解决边权为负的情况，模板：
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
const int N = 2010, M = 100010;
int hd[N], ver[M*2], dis[N], val[M*2], nxt[M*2], mk[N], idx, n, m;
void add(int x, int y, int v) {
ver[++idx] = y;
val[idx] = v;
nxt[idx] = hd[x];
hd[x] = idx;
}
void spfa() {
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
queue <int> q;
q.push(1);
mk[1] = 1;
while (q.size()) {
int t = q.front();
q.pop();
mk[t] = 0;
for (int i = hd[t]; i; i = nxt[i]) {
int y = ver[i], v = val[i];
if (dis[y] > dis[t]+v) {
dis[y] = dis[t]+v;
if (!mk[y]) q.push(y), mk[y] = 1;
}
}
}
}
int main () {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y, v;
scanf("%d%d%d", &x, &y, &v);
add(x, y, v);
add(y, x, v);
}
spfa();
if (dis[n] == 0x3f3f3f3f) printf("-1\n");
else printf("%d\n", dis[n]);
return 0;
}
弗洛伊德Floyd算法
用于解决多源最短路问题
我们发现上述两个方法都只能解决单源最短路问题，而要使用上述方法解决多源最短路，时间复杂度就要再套上一个n^2，这时候显然就爆了，那么就到了Floyd出场的时候了，这个算法思想很简单，基本上就是暴力枚举，具体实现方法类似于区间dp，核心代码如下：
void floyd(){
for(int k = 1;k <= n;k++) {
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
if (dis[i][j] > dis[i][k]+dis[k][j]) dis[i][j] = dis[i][k]+dis[k][j];
}
}
}
}
总结：这几个算法各有利弊，有各自的适用情况，具体运用要结合数据范围及题目要求，灵活使用
标签：idx,int,短路,mk,问题,复杂度,dis From： https://www.cnblogs.com/breeze-zyh/p/17606552.html