搜索与图论(二)

最短路

单源最短路

所有边权都是正数

朴素Dijkstra算法

基本思路:从1号点到其他点的最短距离

步骤:

定义一个s集合包含当前已确定最短距离的点

1、初始化距离dis[1] = 0,dis[其它] = 正无穷

2、for i 0-n循环n次 

    2.1找到不在s中的距离最近的点 ->t

    2.2把t加到s当中去

    2.3用t来更新其它点的距离

模板代码如下:

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N = 510;
int n,m;
int g[N][N];
//dis表示从1号点到其它点的距离
int dist[N];
//st表示每个点的最短路是否确定
bool st[N];int dijkstra()
{memset(dist,0x3f,sizeof dist);dist[1] = 0;for(int i = 0;i < n; i ++){int t = -1;for(int j = 1;j <= n;j ++)if(!st[j] && (t == -1 || dist[t] > dist[j]))t = j;st[t] = true;for(int j = 1;j <= n;j ++)dist[j] = min(dist[j],dist[t] + g[i][j]);}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}
int main()
{scanf("%d%d", &n, &m);//初始化memset(g,0x3f,sizeof g);int t = dijkstra();printf("%d\n",t);return 0;
}

堆优化版的Dijkstra算法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queque>using namespace std;const int N = 100010;
int n,m;
//存储方式改为邻接表的形式
int h[N],w[N],e[N],ne[N],idx;
//dis表示从1号点到其它点的距离
int dist[N];
//st表示每个点的最短路是否确定
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 ver = t.second,distance = t.first();if (st[ver]) continue;for(int i = h[ver];i != -1;i = ne[i]){int j = e[i];if(dist[j] > distance + w[i]){dist[j] = distance + 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);}int t = dijkstra();printf("%d\n",t);return 0;
}

存在负权边

Bellman-Ford算法

基本思路:n次迭代，每次循环所有边，每次循环更新最短距离

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int M = 100010, N = 510;int n,m,k;
int dist[N],backup[N];struct Edge
{int a,b,w;}edges[M];int bellman_ford()
{memset(dist,0x3f,sizeof dist);dist[1] = 0;for(int i = 0;i < k;i ++){//保存上一次的结果memcpy(backup,dist,sizeof dist);for(int j = 0;j < m;j ++){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;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\n",t);return 0;
}

SPFA算法

对Bellman-Ford算法的一个优化

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queque>using namespace std;const int N = 100010;
int n,m;
//存储方式改为邻接表的形式
int h[N],w[N],e[N],ne[N],idx;
//dis表示从1号点到其它点的距离
int dist[N];
//st表示每个点的最短路是否确定
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);queue<int> q;q.push(1);st[1] = 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];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("false");else printf("%d\n",t);return 0;
}

多源汇最短路

Floyd

利用临界矩阵来存储

#include<iostream>
#include<cstring>
#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()
{scanf("%d%d%d",&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,w;scanf("%d%d%d",&a,&b,&w);d[a][b] = min(d[a][b],w);}floyd();while(Q --){int a,b;scanf("%d%d",&a,&b);if(d[a][b] > INF / 2) puts("impossible");printf("%d\n",d[a][b]);}return 0;
}