BFS 给定一个无向图，有n个点，m条边，每条边的长度为1，指定起始点为1，求1到n的最短路 while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < sz(g[i]); ++i) { int v = g[u][i]; if (d[v] > d[u] + 1) { d[v] = d[u] + 1; q.push(v); } } }
Dijkstra 给定一个n个点m条边的正权有向图，指定起始点为1，求1到每个点的最短路 void dij(int s) { priority_queue<pii,vector<pii>,greater<pii> > q; memset(d,0x3f,sizeof(d)); d[s] = 0; q.push(pii(0,s)); while (!q.empty()) { int u = q.top().se; q.pop(); if (vis[u]) continue; //是否已经确认过最短路径 vis[u] = true; for (auto it:g[u]) //c++11支持，相当于java的for each。g[u]是一个可遍历的容器或流，使用it来遍历g[u]以此获得容器或流内的每一个元素 { if (d[u] + it.se < d[it.fi]) { d[it.fi] = d[u] + it.se; q.push(pii(d[it.fi],it.fi)); } } } }
Bellman-ford 给定一个n个点m条边的正权有向图，指定起始点为1，求1到每个点的最短路 注意点： 1.负环（无意义） 2.用边来更新，边共m条 //edge u[j]->v[j] cost:w[j] for (int i = 1; i <= n - 1; ++i) { for (int j = 1; j <= m; ++j) { if (d[u[j]] + w[j] < d[v[j]]) { d[v[j]] = d[u[j]] + w[j]; } } }
spfa 给定一个n个点m条边的正权有向图，指定起始点为1，求1到每个点的最短路 对于一条边（u，v, w)来说，如果dis[u]不变的时候，那么这一轮对于u为起点的边，其实是无效的更新 //edge u[j]->v[j] cost:w[j]; for (int i = 1; i <= n - 1; ++i) { for (int j = 1; j <= m; ++j) { if (d[u[j]] + w[j] < d[v[j]]) { d[v[j]] = d[u[j]] + w[j]; } } } //优化 while (!q.empty()) { int u = q.front(); q.pop(),vis[u] = false; for (auto it:G[u]) { if (d[it.fi] > d[u] + it.se)//fi 记录v se 记录u-v cost:w { d[it.fi] = d[u] + it.se; if (!vis[it.fi])//表示该点是否已经进入过队列 { vis[it.fi] = true; ++mark[it.fi];//记录图是否出现负环；出现负环return q.push(it.fi); if (mark[it.fi] > n) return false; } vis[it.fi] = true; } } }
//存疑 n个城市，每个城市都要举办演唱会，票价是a[i]，此外还有m条双向有权边连接各个城市，求从每个城市出发，看一场演唱会再返回的最小花费。 input 4 2 1 2 4 2 3 7 6 20 125 output 6 14 1 25
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; int d[maxn][maxn]; int cost[maxn]; int a[maxn]; int main() { int n,m; cin >> n >> m; for (int i = 1; i <= m; ++i) { int u,v,w; cin >> u >> v >> w; d[u][v] = d[v][u] = 2 * w; } for (int i = 1; i <= n; ++i) { cin >> a[i]; d[n + 1][i] = d[i][n + 1] = a[i]; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n + 1; ++j) { if (j != i) { } } } }
多源最短路 floyd O(n^3) 给定一张n个点M条边的正权有向图，求每两点间的最短路 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]); } } } dp[k][i][j] = dp[k - 1][i][j] dp[k][i][j] = dp[k - 1][i][k] + dp[k - 1][k][j] --->dp[n][i][j] 可以压掉第一维（注意三个维度的顺序）