目录
朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I
时间复杂是 O(n2+m)O(n2+m), nn 表示点数,mm 表示边数
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路,如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在还未确定最短路的点中,寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
题目代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
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[t][j]);
}
}
if(dist[n] == 0x3f3f3f) return -1;
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);
}
int t = dijkstra();
printf("%d\n", t);
return 0;
}
堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II
时间复杂度 O(mlogn)O(mlogn), nn 表示点数,mm 表示边数
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离,如果不存在,则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离,second存储节点编号
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
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];
}
题目代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 510;
typedef pair <int, int> PII;
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()) {
PII t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; 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算法 —— 模板题 AcWing 853. 有边数限制的最短路
时间复杂度 O(nm)O(nm), nn 表示点数,mm 表示边数
注意在模板题中需要对下面的模板稍作修改,加上备份数组,详情见模板题。
int n, m; // n表示点数,m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边,a表示出点,b表示入点,w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离,如果无法从1走到n,则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式,就说明存在一条长度是n+1的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
题目代码
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510, M = 10010;
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算法) —— 模板题 AcWing 851. spfa求最短路
时间复杂度 平均情况下 O(m)O(m),最坏情况下 O(nm)O(nm), nn 表示点数,mm 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离,如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
auto 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]) // 如果队列中已存在j,则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
题目代码
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n, m;
int h[N], w[N], e[N], ne[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;
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\n", t);
return 0;
}
spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环
时间复杂度是 O(nm)O(nm), nn 表示点数,mm 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离,cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中
// 如果存在负环,则返回true,否则返回false。
bool spfa()
{
// 不需要初始化dist数组
// 原理:如果某条最短路径上有n个点(除了自己),那么加上自己之后一共有n+1个点,由抽屉原理一定有两个点相同,所以存在环。
queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}
while (q.size())
{
auto 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; // 如果从1号点到x的最短路中包含至少n个点(不包括自己),则说明存在环
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
floyd算法 —— 模板题 AcWing 854. Floyd求最短路
时间复杂度是 O(n3)O(n3), nn 表示点数
初始化:
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;
// 算法结束后,d[a][b]表示a到b的最短距离
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]);
}
题目代码
#include<iostream>
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");
else{
printf("%d\n", d[a][b]);
}
}
return 0;
}
标签:dist,int,短路,d%,st,算法,基础课,return,AcWing
From: https://blog.csdn.net/Sophia2021XJTU/article/details/139567230