最短路: Djikstra

适用于边权非负

如果存在负边权, 则当前距离dist最小的点, 不一定就是实际离源点最近的点,可能有负边导致其它路径离当前点更近

如下图所示, 如果存在负边, y点距离S点最近, 所以选中y点进行松弛,
贪心思想
当边权非负,离起点S最近的点,不能被更新, 如果在中间加入一个点,则长度必然大于当前距离
在稀疏图中.使用二叉堆实现的 Dijkstra 算法较 Bellman-Ford 算法具有较大的效率优势；
而在稠密图中,这时候使用暴力做法较二叉堆实现更优。

最短路

暴力
时间复杂度
- 不使用任何数据结构进行维护，每次 2 操作执行完毕后，直接在集合中暴力寻找最短路长度最小的结点。2 操作总时间复杂度为，1 操作总时间复杂度为，全过程的时间复杂度为。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e3+5;
const int INF = 0x3f3f3f3f;
int dist[N];
bool distOver[N];
vector<PII> edges[N];
int n, m, k;
void djikstra(int s, int t) {memset(dist, 0x3f, sizeof(dist));memset(distOver, false, sizeof(distOver));dist[s] = 0;for (int i = 1; i <= n; i++) {int u = -1;for (int j = 1; j <= n; j++) {if (!distOver[j] && dist[j] < INF) {if (u == -1 || dist[j] < dist[u]) {u = j;}}}if (u == -1) break;distOver[u] = true;for (auto [v, w] : edges[u]) {dist[v] = min(dist[v], dist[u] + w);}}if (dist[t] < INF) cout << dist[t] << endl;else cout << -1 << endl;}
int main() {cin >> n >> m >> k;while (m--) {int u, v, w;cin >> u >> v >> w;edges[u].push_back({v, w});}while (k--) {int s, t;cin >> s >> t;djikstra(s, t);}return 0;
}

最短路2

堆优化

使用升序排列的优先队列

distOver[u]表示结点u的距离已经确定

每从堆中取出最近的点, 则S到这个点的最短距离已经确定

再从这个点开始尝试松弛, 其它未确定的点的距离

时间复杂度

和二叉堆类似，但使用优先队列时，如果同一个点的最短路被更新多次，因为先前更新时插入的元素不能被删除，也不能被修改，只能留在优先队列中，故优先队列内的元素个数是O(m)的，

时间复杂度为 $O (m * l o g m)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
bool distOver[N];
int dist[N];
vector<pair<int, int>> edge[N];
void Djikstra(int s, int t) {memset(dist, 0x3f, sizeof(dist));memset(distOver, false, sizeof(distOver));priority_queue<PII, vector<PII>, greater<PII>> q;dist[s] = 0;q.push(make_pair(dist[s], s));while (!q.empty()) {int u = q.top().second; q.pop();if(distOver[u]) continue;distOver[u] = true;for(auto [v, w] : edge[u]) {if(dist[u] + w < dist[v]) {dist[v] = dist[u] + w;q.push({dist[v], v});}}}if(dist[t] < INF) printf("%d\n", dist[t]);else puts("-1");
} 
int main() {int n, m, k;cin >> n >> m >> k;while (m--) {int u, v, w;cin >> u >> v >> w;edge[u].push_back({v, w});}while (k--) {int s, t;cin >> s >> t;Djikstra(s, t);}return 0;
}

租房

因为是无向图, 所以s到t的最短距离就是t到s的最短距离

正向思维
- 对每个点跑Djikstra,求得到那三个点的最短距离, 然后取最小值
逆向思维
- 从其余点到那三个点的最短距离就等于那三个点到其余点的最短距离
- 对那三个点各跑一次Djikstra, 求得三个点到其余个点的最短距离
- 再遍历各点, 算出各点到那三个点的最短距离之和, 取min

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e3+5;
const int INF = 0x3f3f3f3f;
int n, m, a, b, c;
vector<PII> edges[N];
int dist[N];
int f[3][N];
bool distOver[N];
void djikstra(int k, int s) {memset(dist, 0x3f, sizeof(dist));memset(distOver, false, sizeof(distOver));dist[s] = 0;priority_queue<PII, vector<PII>, greater<PII>> q;q.push({dist[s], s});while (!q.empty()) {int u = q.top().second;q.pop();if (distOver[u]) continue;distOver[u] = true;for (auto [v, w] : edges[u]) {if (dist[u] + w < dist[v]) {dist[v] = dist[u] + w;q.push({dist[v], v});}}}    memcpy(f[k], dist, sizeof(dist));
}
int main() {cin >> n >> m;while (m--) {int u, v, w;cin >> u >> v >> w;edges[u].push_back({v, w});edges[v].push_back({u, w});}cin >> a >> b >> c;djikstra(0, a);djikstra(1, b);djikstra(2, c);    int ans = INF;// 3行n列, 按列求和, 求列和的最小值, // 对应列序号的点即为到3个点的最近点// 列和即为到3个点的最短距离之和for (int i = 1; i <= n; i++) {int temp = f[0][i] + f[1][i] + f[2][i];ans = min(ans, temp);}cout << ans << endl;return 0;
}

聚会

所有同学周末要到小蜗家聚会，聚会结束后同学们都会回家。为了合理安排时间，小蜗想要知道对于在路上来回花费时间最长的同学，他在路上要花费多少时间。

题目说的是来回花费时间最大的点

从s点到其它点的距离很好求, 直接在s点处跑djistra即可获得到其余点的最短距离

但由于是有向图, 其余点到s点的最短距离并不等于s点到其余点的最短距离

如何求其余n-1个点到s点的最短距离?

暴力想法: 枚举其余n-1个点, 对每个点跑一次djistra, 求出n-1个点到目标点的最短距离, 求他们的最大值, 显然时间复杂度为: $O (nm l o g m)$

优化: 其余n-1个点到s的距离等于在反图中, s点到其余点的最短距离

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
int n, m, k;
vector<PII> edges[2][N];
int dist[N];
int f[2][N];
bool distOver[N];
void djikstra(int k, int s) {memset(dist, 0x3f, sizeof(dist));memset(distOver, false, sizeof(distOver));dist[s] = 0;priority_queue<PII, vector<PII>, greater<PII>> q;q.push({dist[s], s});while (!q.empty()) {int u = q.top().second;q.pop();if (distOver[u]) continue;distOver[u] = true;for (auto [v, w] : edges[k][u]) {if (dist[u] + w < dist[v]) {dist[v] = dist[u] + w;q.push({dist[v], v});}}}    memcpy(f[k], dist, sizeof(dist));
}
int main() {cin >> n >> m >> k;while (m--) {int u, v, w;cin >> u >> v >> w;edges[0][u].push_back({v, w});edges[1][v].push_back({u, w});}djikstra(0, k);djikstra(1, k);int ans = 0;for (int i = 1; i <= n; i++) {int temp = f[0][i] + f[1][i];ans = max(ans, temp);}cout << ans << endl;return 0;
}