dijkstral算法 (复杂度O(nlongn + m))——不能有负权边
spfa算法 (复杂度O(km))——不能有负权环
如何存图
用的是伪邻接表（链式前向星）
插入用的是头插法
int tot;
struct node
{
int to, l, next;//to代表这条边指向谁，l代表边权，next代表下一条边的位置
}edge[1050];
//添加一条x指向y的边权为z的边
void addedge(int x, int y, int z)
{
edge[++tot].to = y;
edge[tot].l = z;
edge[tot].next = head[x];
head[x] = tot;
}注意：
1.如果题中的边无边权，结构体中无需定义变量l；
2.对于无向图，比如点x和点y之间有一条边权为z的无向边，即可以从x指向y也可以从y指向x。首先，一条无向边我们当作两条边，所以edge数组要开两倍，addedge是需要addedge（x，y，z）和addedge（y，x，z）
3.对于点上带权的图，假设有一个权值为4的点，我们把这个点看成两个无权值点，中间有一条边权为4的点相连
4.edge数组和head数组初始赋为-1。
NC17511公交线路（模板题）
dijkstral算法
复杂度有说O（nlogn + m）的有说O（n^2）的。
不能算有负权边的图
算法过程：
•1、在开始之前，认为所有的点都没有进行过计算，dis[]全部赋值为极大值(dis[]表示各点当
前到源点的最短距离）
• 2、源点的dis值明显为0
• 3、计算与s相邻的所有点的dis值 —— dis[v] = map[s][v]
• 4、还没算出最短路的点中dis[]最小的一个点u， 其最短路就是当前的dis[u]
• 5、对于与u相连的所有点v，若dis[u]+map[u][v] 比当前的dis[v]小, 更新dis[v]
• 6、重复4,5直到源点到所有点的最短路都已求出
维护容器：
1.堆，存一个结构体，这个结构体包含两个量，一个是dis[i],一个是这个点是谁。将还没有算出最短路的点但是更新过的点放到堆里，每次取堆中dis[]最小的那个点u,其最短路就是dis[u],然后由这个点去更新其他点。
2.dis[i],用来存起点到点i目前的最短路
3.vis[i],表示dis[i]是否就是真正的最短路
AC代码
#include <bits/stdc++.h>
using namespace std;
int n, m, s, t;
int tot;
int a, b, v;
struct node
{
int to, l, next;
}edge[200050];
int head[1050];;
void addedge(int x, int y, int z)
{
edge[++tot].to = y;
edge[tot].l = z;
edge[tot].next = head[x];
head[x] = tot;
}
struct node1
{
int l, pos;
bool operator < (const node1 &b) const//需要小根堆，而普通的优先队列是大根堆没注意这个比较关系
{
return l > b.l;
}
}now;
priority_queue<node1> q;//大根堆
int dis[1050];
bool vis[1050];
//dij步骤详细：
//1.数组初始化，dis除了s点外全赋为正无穷，s点赋为0，vis全标记为0，并将s点入队
//2.开始取队首并pop，判断该点最短路是否已经确定，已经确定则continue，否则再执行下面的操作
//3.遍历该点所有的出去的边，判断到达的地方的最短路是否需要更改，需要则更改，并将该点入队（很像bfs）
//4.判断能否到达t点
void dij()
{
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[s] = 0;
q.push({0, s});
while(!q.empty())
{
now = q.top();
q.pop();
if(vis[now.pos]) continue;
vis[now.pos] = 1;
for(int i = head[now.pos]; i != -1; i = edge[i].next)
{
int y = edge[i].to;
if(dis[y] > dis[now.pos] + edge[i].l)
{
dis[y] = dis[now.pos] + edge[i].l;
q.push({dis[y],y});
}
}
}
if(dis[t] >= 0x3f3f3f3f) dis[t] = -1;
}
int main()
{
memset(edge, -1, sizeof(edge));
memset(head, -1, sizeof(head));
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i = 1; i <= m; ++i)
{
scanf("%d%d%d", &a, &b, &v);
addedge(a, b, v);
addedge(b, a, v);
}
dij();
printf("%d\n", dis[t]);
return 0;
}
spfa
复杂度O（km）k是平均入队次数，一般不超过10（出题人不想卡你）。
SPFA算法的实现
• 设Dis代表S到i点的当前最短距离，Fa代表S到i的当前最短路径中i点之前的一个点的编号。
开始时Dis全部为+∞，只有Dis[S]=0，Fa全部为0。
• 维护一个队列，里面存放所有需要进行迭代的点。初始时i队列中只有一个点S。用一个布尔数
组记录每个点是否处在队列中。
• 每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断
Dis[v]+len是否小于Dis[u]，若小于则改进Dis[u]，将Fa[u]记为v，并且由于S到u的最短
距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直
迭代下去直到队列变空，也就是S到所有节点的最短距离都确定下来，结束算法。若一个点入
队次数超过n，则有负权环。
• SPFA 在形式上和广度优先搜索非常类似，不同的是广度优先搜索中一个点出了队列就不可能
重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过
其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代
下去。
总结就是，对于到某个点的最短路，如果到达这个点之前的某个的最短路发生了变化，那么到这个点的最短路可能就变了，所以我们需要把最短路发生变化的点存到一个队列里，对于每一个发生改变的点，都要判断一下它所连的点的最短路是否改变。
维护容器：
1.队列，队列中的点是最短路改变了的点，因为改变了所以可能会对后面点的最短路发生影响，需要存起来，之后判断
2.dis数组
3.vis用来表示点i是否在队列里，该数组作用跟dij里的不一样，需要做区分
AC代码：
#include <bits/stdc++.h>
using namespace std;
int n, m, s, t, tot;
int a, b, v;
struct node
{
int to, l, next;
}edge[20050];
int head[1050];
void addedge(int x, int y, int z)
{
edge[++tot].to = y;
edge[tot].l = z;
edge[tot].next = head[x];
head[x] = tot;
}
int dis[1050];
bool vis[1050];
queue<int> q;
int now, y;
//步骤详细：
//1.初始化，dis，vis，起点，入队，标记
//2.取队首，出队，标记，开始遍历
//3.利用head数组找到该点的边，判断连向的每个个点是否需要更改，需要则更改，之后判断是否在队列，不在则入队，标记
void spfa()
{
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[s] = 0;
q.push(s);
vis[s] = 1;
while(!q.empty())
{
now = q.front();
q.pop();
vis[now] = 0;
for(int i = head[now]; i != -1; i = edge[i].next)
{
y = edge[i].to;
if(dis[y] > dis[now] + edge[i].l)
{
dis[y] = dis[now] + edge[i].l;
if(!vis[y])
{
q.push(y);
vis[y] = 1;
}
}
}
}
if(dis[t] >= 0x3f3f3f3f) dis[t] = -1;
}
int main()
{
memset(edge, -1, sizeof(edge));
memset(head, -1, sizeof(head));
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i = 1; i <= m; ++i)
{
scanf("%d%d%d", &a, &b, &v);
addedge(a, b, v);
addedge(b, a, v);
}
spfa();
printf("%d\n", dis[t]);
return 0;
}
京公网安备 11010502036488号