关于单源最短路的拓展应用

1. 概述

• 在最短路问题中，一般存在以下几种扩展应用：
  • 超级源点
  • 拆点建图
  • 套DP
  • 记录最短路条数

2.超级源点

题目描述：有多个起点，求到某一个终点的最短路径。

• 解决方案：建立一个超级源点，且该超级源点到所有起点的距离都为0。这样即可将多源最短路问题转换成单源最短路问题。

3. 拆点建图

题目背景：地图的每一个位置，可能根据其状态不同，到达这里的最短路径也不同。(如：需要钥匙，求次短路等)

• 解决方案：地图上每个位置的其状态，可以用状态压缩的方法来表示。(我们可以将每个位置不同的状态看作为一个新的点)
  • 例如:地图上有n把钥匙，那么每个位置就有2的n次方个属性。其每个属性都可以作为一个起点(初始距离为原起点到该点的距离)压入优先队列，进行最短路的计算。

4. 套DP

最短路问题与DP问题并集较大。(必须满足拓扑序)

• 适用范围：
  • BFS：每个点只入队一次，只出队一次。
  • Dijkstra：每个点第一次出队的序列必定满足拓扑序。
  • SPFA：本身不具备拓扑序。(×)

5. 记录最短路条数

本质是DP

• 在满足拓扑序的情况下，进行DP。
• 如果需要求次短路，则还需要进行拆点操作。

原文：https://www.cnblogs.com/z-thorn/p/14550945.html