稀疏图上Johnson算法详解：构造G'与距离优化

基于稀疏图上的Johnson算法是一种用于寻找带有负权边图的单源最短路径的高效方法，特别适用于那些不存在负权回路的情况。该算法通过以下几个步骤实现： 1. **构建辅助图G'**：首先，将原图G中添加一个特殊的虚拟节点0，将其与所有其他节点连接，并赋予权重0。这样做的目的是为了简化算法的处理过程。新的边集E'包含了0与所有其他节点的边。 2. **应用Bellman-Ford算法**：在新图G'上执行Bellman-Ford算法，它用于查找从虚拟节点0到所有其他节点的最短路径。算法会持续迭代直到没有进一步的改进，或者检测到负权回路。如果有负权回路，算法会立即停止并返回FALSE，表示图中不满足单源最短路径问题的假设。 3. **设置辅助距离h(v)**：对于G'中的每个节点v，将从0到v的最小距离h(v)设为其值。这一步有助于后续的权值调整。 4. **权值更新**：对于G'中的每条边w(u, v)，更新其权值为w(u, v) + h(u) - h(v)。这种操作使得原来的边权看起来像是从0节点出发的相对成本。 5. **Dijkstra算法的使用**：在原始图G中，利用已经更新过的权值，通过Dijkstra算法重新计算每对节点之间的最短路径d'[u][v]。 6. **最终距离计算**：在原图G中，最短距离d[u][v]等于d'[u][v]加上起点v到终点u的辅助距离差（h(v) - h(u)）。 算法的C语言版本展示了三个关键部分：Bellman-Ford算法（用于辅助图G'），Dijkstra算法（用于原始图G），以及一个二项堆实现的优先级数组（用于Dijkstra算法中的节点优先级）。代码示例参考了《算法导论》中的图25-1，但存在一些未优化的部分，例如辅助结构`vassist`在两个算法中的用法差异，以及`relax`函数中的优化空间。 值得注意的是，虽然可以直接在图G'上执行Dijkstra算法，但原始设计中避免了0节点的处理以节省计算资源，但这样可能增加了一定的复杂性。在实际应用时，开发者需要根据具体需求和性能考虑选择合适的优化策略。