路径紧缩（Path Compression）是用于优化Dijkstra算法的一种算法技巧，目的是减少搜索树中的路径数量，从而提高算法效率。在加权有向图中，路径紧缩可以有效地减少最短路径树的节点数量，使算法更快地找到最短路径。
路径紧缩的基本思想是：当发现一条路径比已有的最短路径更短时，将这条路径与原有路径进行合并，而不是将原有路径替换。这样，在搜索过程中，可以有效地减少树的节点数量，从而提高搜索速度。
路径紧缩的应用场景：
- 单源最短路径问题：在有向图中，从源节点到其他所有节点的最短路径问题。
- 所有顶点对之间的最短路径问题：在有向图中，任意两个节点之间的最短路径问题。
以下是使用Python实现Dijkstra算法并进行路径紧缩的示例代码：
import heapq
class Edge:
def init(self, u, v, weight):
self.u = u
self.v = v
self.weight = weight
class Graph:
def init(self, vertices):
self.vertices = vertices
self.edges = []
def add_edge(self, u, v, weight):
self.edges.append(Edge(u, v, weight))
def dijkstra(self, start):
distances = [float('inf')] * self.vertices
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_vertex = heapq.heappop(pq)
if current_distance > distances[current_vertex]:
continue
for edge in self.edges:
if edge.u == current_vertex:
new_distance = current_distance + edge.weight
if new_distance < distances[edge.v]:
distances[edge.v] = new_distance
heapq.heappush(pq, (new_distance, edge.v))
if edge.v == current_vertex:
new_distance = current_distance + edge.weight
if new_distance < distances[edge.u]:
distances[edge.u] = new_distance
heapq.heappush(pq, (new_distance, edge.u))
return distances
示例
vertices = 5
graph = Graph(vertices)
graph.add_edge(0, 1, 10)
graph.add_edge(0, 2, 6)
graph.add_edge(1, 2, 1)
graph.add_edge(1, 3, 2)
graph.add_edge(2, 3, 4)
graph.add_edge(2, 4, 3)
graph.add_edge(3, 4, 2)
print("原始Dijkstra算法结果：")
print(graph.dijkstra(0))
print("\n使用路径紧缩的Dijkstra算法结果：")
graph_compressed = Graph(vertices)
for edge in graph.edges:
graph_compressed.add_edge(edge.u, edge.v, edge.weight)
print(graph_compressed.dijkstra(0))
CopyCopy
在这个示例中，我们创建了一个简单的有向图，并使用Dijkstra算法计算从顶点0到其他顶点的最短路径。在原始Dijkstra算法结果中，我们可以看到搜索树中的冗余路径。
