路径压缩 (Path Compression) 是一种用于求解最短路径问题的算法，通常用于 Dijkstra 算法中，可以加速求解最短路径问题。
路径压缩通过将已经确定的最短路径信息传递给未确定最短路径的节点，来加速最短路径的计算。具体来说，当一个节点的最短路径已经确定时，它会将这个信息传递给所有它的邻居节点，这样邻居节点就可以跳过一些不必要的计算，直接使用已经确定的最短路径信息，从而加速整个最短路径的计算过程。
路径压缩通常用于以下情况:
- 在 Dijkstra 算法中，当某个节点的最短路径已经确定时，可以使用路径压缩来加速其邻居节点的计算。
- 在 Floyd 算法中，当某个节点的最短路径已经确定时，可以使用路径压缩来加速整个计算过程。
以下是一个简单的示例，演示了如何在 Dijkstra 算法中使用路径压缩:
include
include
include
using namespace std;
const int INF = 0x3f3f3f3f; // 表示无穷大
struct Edge {
int to; // 边的终点
int weight; // 边的权重
Edge(int t, int w) : to(t), weight(w) {}
};
vector adj[100010]; // 存储图的邻接表
int dist[100010]; // 存储源点到各个点的最短距离
void dijkstra(int start) {
priority_queue, vector>, greater>> pq; // 小根堆，存储 (距离，点) 的二元组
pq.push(make_pair(0, start)); // 把源点放入堆中，距离为 0
dist[start] = 0; // 源点到自己的距离为 0
while (!pq.empty()) {
auto curr = pq.top();
pq.pop();
int currDist = curr.first, currNode = curr.second;
// 如果当前节点已经被处理过了，跳过
if (currDist != dist[currNode]) {
continue;
}
// 遍历当前节点的邻居
for (auto& edge : adj[currNode]) {
int nextNode = edge.to, nextDist = currDist + edge.weight;
// 如果通过当前节点到达邻居节点的距离更短，更新距离并加入堆中
if (nextDist < dist[nextNode]) {
dist[nextNode] = nextDist;
pq.push(make_pair(nextDist, nextNode));
}
}
}
}
int main() {
int n, m, start;
cin >> n >> m >> start;
// 初始化邻接表和距离数组
for (int i = 1; i < n; ++i) {
adj[i].clear();
dist[i] = INF;
}
// 读入边，建立邻接表
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(Edge(v, w));
}
// 使用 Dijkstra 算法计算最短路径
dijkstra(start);
// 输出结果
for (int i = 1; i <= n; ++i) {
cout << dist[i] << " ";
}
return 0;
}
CopyCopy
在上面的示例中，我们使用路径压缩来加速 Dijkstra 算法。具体来说，在遍历当前节点的邻居时，我们检查当前节点是否已经被处理过了，如果是，则跳过;否则，我们更新邻居节点的距离，并将其放入堆中。这样，我们就可以避免重复计算已经确定的最短路径，从而加速整个计算过程。
