网站设置关键词,学历提升专升本,网站如何屏蔽中国ip,wordpress 导出html5搜索与图论 图的存储方式2、最短路问题2.1、Dijkstra算法#xff08;朴素版#xff09;2.2、Dijkstra算法#xff08;堆优化版#xff09;2.3、Bellman-Ford算法2.4、SPFA求最短路2.5、SPFA判负环2.6、Floyd算法 图的存储方式 2、最短路问题
最短路问题可以分为单源最短路… 搜索与图论 图的存储方式2、最短路问题2.1、Dijkstra算法朴素版2.2、Dijkstra算法堆优化版2.3、Bellman-Ford算法2.4、SPFA求最短路2.5、SPFA判负环2.6、Floyd算法 图的存储方式 2、最短路问题
最短路问题可以分为单源最短路问题和多源最短路问题单源最短路问题就是求出从点1-n的最短距离而多源最短路问题就是求出从点i-j的最短距离。单源最短路问题还可以分为正权边的单源最短路问题和负权边的单源最短路问题。具体算法和时间复杂度如下图 2.1、Dijkstra算法朴素版 算法模板
#include iostream
#include cstringusing namespace std;
const int N 510;
int g[N][N], d[N];
int n, m;
bool st[N];int dijkstra()
{memset(d, 0x3f, sizeof d);d[1] 0;for (int i 0; i n; i){int t -1;for (int j 1; j n; j)if (!st[j] (t -1 || d[t] d[j]))t j;st[t] true;for (int j 1; j n; j)d[j] min(d[j], d[t] g[t][j]);}return d[n] 0x3f3f3f3f ? -1 : d[n];
}int main()
{cin 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);}cout dijkstra() endl;return 0;
}2.2、Dijkstra算法堆优化版
下面来看看如何优化
算法模板
#include iostream
#include cstring
#include queueusing namespace std;
typedef pairint, int PII;
const int N 1.5e510;
int h[N], e[N], w[N], ne[N], idx;
int n, m, d[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(d, 0x3f, sizeof d);d[1] 0;priority_queuePII, vectorPII, greaterPII heap;heap.push({0, 1});while (heap.size()){auto t heap.top();heap.pop();int ver t.second, dis t.first;if (st[ver]) continue;st[ver] true;for (int i h[ver]; i ! -1; i ne[i]){int j e[i];if (d[j] dis w[i]){d[j] dis w[i];heap.push({d[j], j});}}}return d[n] 0x3f3f3f3f ? -1 : d[n];
}int main()
{cin n m;memset(h, -1, sizeof h);while (m--){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}cout dijkstra() endl;return 0;
}2.3、Bellman-Ford算法 代码模板
#include iostream
#include cstringusing namespace std;
const int N 510, M 10010;
int n, m, k;
int d[N], backup[N];struct Edge
{int a, b, w;
}edges[M];void bellman_ford()
{memset(d, 0x3f, sizeof d);d[1] 0;for (int i 0; i k; i){memcpy(backup, d, sizeof d);for (int j 0; j m; j){auto e edges[j];d[e.b] min(d[e.b], backup[e.a] e.w);}}
}int main()
{cin 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};}bellman_ford();if (d[n] 0x3f3f3f3f / 2) cout impossible endl;else cout d[n] endl;return 0;
}2.4、SPFA求最短路 代码模板
#include iostream
#include cstring
#include queueusing namespace std;
const int N 1e510;
int n, m;
int h[N], e[N], w[N], ne[N], idx;
int d[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;
}void spfa()
{memset(d, 0x3f, sizeof d);d[1] 0;queueint 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 (d[j] d[t] w[i]){d[j] d[t] w[i];if (!st[j]){st[j] true;q.push(j);}}}}
}int main()
{cin n m;memset(h, -1, sizeof h);while (m--){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}spfa();if (d[n] 0x3f3f3f3f) cout impossible endl;else cout d[n] endl;return 0;
}2.5、SPFA判负环 #include iostream
#include cstring
#include queueusing namespace std;
const int N 2010, M 10010;
int h[N], e[M], w[M], ne[M], idx;
int n, m;
int d[N], cnt[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;
}bool spfa()
{queueint 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 (d[j] d[t] w[i]){d[j] d[t] w[i];cnt[j] cnt[t] 1;if (cnt[j] n) return true;if (!st[j]){st[j] true;q.push(j);}}}}return false;
}int main()
{cin n m;memset(h, -1, sizeof h);while (m--){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}if (spfa()) cout Yes endl;else cout No endl;return 0;
}2.6、Floyd算法 #include iostream
#include cstringusing namespace std;
const int N 210, INF 0x3f3f3f3f;
int d[N][N];
int n, m, k;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()
{cin n m k;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, c;cin a b c;d[a][b] min(d[a][b], c);}floyd();while (k--){int l, r;cin l r;if (d[l][r] INF / 2) cout impossible endl;else cout d[l][r] endl;}return 0;
}
