Dijkstra
补充：求次短路，只需要多维护一个“短路”就行了；
但在维护次短路时，要记得把更新前的最短路与更新后的最短路swap一下，留着给次短路更新；
注意：不能处理负边权， 有负边权就换SPFA， 当然也不能求最长路。
以下代码以HDOJ 1874(畅通工程续) 为例
题目链接
简洁好理解的堆优化代码。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
typedef pair<int,int> pr;
const int maxn=205;
vector<pr> E[maxn];
int n, m;
int d[maxn], vis[maxn];
void init() {
for(int i=0; i<maxn; ++i) E[i].clear();
for(int i=0; i<maxn; ++i) d[i]=1e9， vis[i]=0;
}
int main() {
while(cin>>n>>m) {
init();
for(int i=0; i<m; ++i) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
E[x].push_back(make_pair(y,z));
E[y].push_back(make_pair(x,z));
}
int s, t;
scanf("%d%d", &s, &t);
priority_queue<pr,vector<pr>,greater<pr> > Q;
Q.push(make_pair(0,s));
d[s]=0;
while(!Q.empty()) {
int now=Q.top().second; Q.pop();
if(vis[now]) continue; vis[now]=1;
for(int i=0; i<E[now].size(); ++i) {
int v=E[now][i].first;
if(d[v]>d[now]+E[now][i].second) {
d[v]=d[now]+E[now][i].second;
Q.push(make_pair(d[v],v));
}
}
}
if(d[t]==1e9) printf("-1\n");
else printf("%d\n", d[t]);
}
}
也可不用greater函数，直接将每次放入队列的d[v]改成-d[v]即可。
SPFA
SLF优化（Small Label First 策略）：使用双端队列，当需要push节点进队列时，判断一下当前dis与队首dis大小；若更小，则push_front()；否则push_back()。
LLL优化（Large Label Last 策略）：如果当前出队的元素dis大于队内平均值，则先push到队尾，考虑下一个元素。
SPFA最短路
以下代码以HDOJ 1874(畅通工程续) 为例
题目链接
注意有个inq数组来记录某个点是否已经在队列了，这是与dij不同的。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
const int maxn=205;
vector<pair<int, int> >E[maxn];
int n, m;
int d[maxn], inq[maxn];
void init() {
for(int i=0; i<maxn; ++i) E[i].clear();
for(int i=0; i<maxn; ++i) inq[i]=0;
for(int i=0; i<maxn; ++i) d[i]=1e9;
}
int main() {
while(cin>>n>>m) {
init();
for(int i=0; i<m; ++i) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
E[x].push_back(make_pair(y,z));
E[y].push_back(make_pair(x,z));
}
int s, t;
scanf("%d%d", &s, &t);
queue<int> Q;
Q.push(s);
d[s]=0;
inq[s]=1;
while(!Q.empty()) {
int now=Q.front();
Q.pop();
inq[now]=0;
for(int i=0; i<E[now].size(); ++i) {
int v=E[now][i].first;
if(d[v]>d[now]+E[now][i].second) {
d[v]=d[now]+E[now][i].second;
if(!inq[v]) {
inq[v]=1;
Q.push(v);
// 在此处加入判负环代码
}
}
}
}
if(d[t]==1e9) printf("-1\n");
else printf("%d\n", d[t]);
}
}
SPFA判断负环
在上述代码指定位置处加入： if(++cnt[v]>n) flag=1
仅仅需要一个cnt[]数组和一个负环flag即可.
SPFA最长路
以下代码以HDOJ 1224 (Free DIY Tour)为例
原理：仅将邻接矩阵的权值定为取负即可(所有d[i]仍初始化为正inf)。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
const int maxn=110;
int N;
int city[maxn], inq[maxn], d[maxn], path[maxn];
vector<pair<int,int> > lj[maxn];
void init() {
memset(inq, 0, sizeof(inq));
memset(path, 0, sizeof(path));
for(int i=0; i<maxn; ++i) lj[i].clear();
for(int i=0; i<maxn; ++i) d[i]=1e7;
}
void print(int p) {
if(p==1) return;
print(path[p]);
if(p==N+1) printf("->1\n");
else printf("->%d", p);
}
int main() {
int T, t;
scanf("%d", &T);
t=T;
while(T--) {
scanf("%d", &N);
init();
for(int i=1; i<=N; ++i) {
scanf("%d", &city[i]);
city[i]=-city[i];
}
city[N+1]=city[1];
int m;
scanf("%d", &m);
while(m--) {
int a, b;
scanf("%d%d", &a, &b);
lj[a].push_back(make_pair(b,city[b]));
}
queue<int> Q;
Q.push(1);
d[1]=0;
inq[1]=1;
while(!Q.empty()) {
int now=Q.front();
inq[now]=0;
Q.pop();
for(int i=0; i<lj[now].size(); ++i) {
int n=lj[now][i].first;
if(d[now]+lj[now][i].second<d[n]) {
d[n]=d[now]+lj[now][i].second;
path[n]=now;
if(inq[n]) continue;
Q.push(n);
inq[n]=1;
}
}
}
printf("CASE %d#\n", t-T);
printf("points : %d\n", -d[N+1]);
printf("circuit : 1");
print(N+1);
if(T) puts("");
}
return 0;
}
Floyd
总所周知 简单粗暴
以下为floyd的路径保存问题代码， 并且附带倒序输出路径
若想要正序输出， 则先将路径弄到栈里面再弹出
void floyd() {
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) {
if(d[i][j]==inf) path[i][j]=-1;
else path[i][j]=i;
}
}
for(int k=0; k<n; ++k) {
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) {
if(!(d[i][k]==inf||d[k][j]==inf)&&d[i][k]+d[k][j]<d[i][j]) {
d[i][j]=d[i][k]+d[k][j];
path[i][j]=path[k][j];
}
}
}
}
}
void printpath(int from, int to) {
printf("%d ", to);
while(path[from][t]!=from) {
printf("%d ", path[from][to]);
to=path[from][to];
}
}
Bellman-Ford
SPFA就是这个算法的队列优化。
同样可以用于判负环（循环了n次及以上，说明有负环）
const int maxn = 1e4+10;
const int maxe = 1e6+10; //最大边数
const int INF = 1e9;
struct edge{
int from, to, cost;
edge(int f=0, int t=0, int c=0):from(f),to(t),cost(c) {}
};
edge es[maxe];
int d[maxn];
int n, E; //顶点数， 边数
void Bellman_Ford(int s) {
for(int i=0; i<n; ++i) d[i]=INF;
d[s]=0;
while(1) {
bool update=0;
for(int i=0; i<E; ++i) {
edge e=es[i];
if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost) {
d[e.to]=d[e.from]+e.cost;
update=1;
}
}
if(!update) break;
}
}
京公网安备 11010502036488号