图论算法思考问题

1. 为什么Dijkstra不能处理负权边？

• 思考点：
• Dijkstra的核心是每一步通过“贪心”策略选择距离最小的未访问顶点，并假设该顶点的最短路径已确定，之后不再更新。但负权边可能打破这一假设。
• 提示：
• Dijkstra依赖于边的非负性保证每一步的最优性。当存在负权边时，可能在已处理的顶点上找到更短的路径，然而Dijkstra不会重新更新已处理过的顶点。

2. 堆优化的Dijkstra复杂度证明

• 思考点：
• 如何通过使用堆优化，将Dijkstra的时间复杂度从$ \(O(n^2)\) $降到$ \(O((n + m) \log n)\) $？
• 提示：
• 使用最小堆可以在$ \(O(\log n)\) $的时间内选择当前最短路径的顶点。
• 每条边的松弛操作时间为$ \(O(\log n)\)$。
• 对每个顶点的堆操作为$ \(O(n \log n)\)$，每条边的松弛操作是$ \(O(m \log n)\)$，总复杂度为 $\(O((n + m) \log n)\)$。

3. SPFA如何是被卡掉？

• 思考点：
• 在什么样的图结构下，SPFA会达到与Bellman-Ford相同的最坏时间复杂度$ \(O(nm)\) $ ？
• 提示：
• SPFA通过队列减少不必要的松弛操作，但某些特定图结构会导致SPFA反复将顶点加入队列进行松弛操作，达到最坏情况。
• 例如，带有大量负权边且路径上有多个负权边的图，会导致SPFA性能下降。

4. Bellman-Ford检测负权回路的机制是什么？

• 思考点：
• Bellman-Ford如何通过多次松弛操作检测负权回路？
• 提示：
• Bellman-Ford在每条边上最多进行$ \(n-1\)$ 次松弛。如果第$ \(n\) $次松弛仍能更新某些顶点的距离，说明存在负权回路。

5. Floyd处理多源最短路径的核心思路是什么？

• 思考点：
• 为什么Floyd适合多源最短路径问题，而不像Dijkstra那样处理单源最短路径？
• 提示：
• Floyd利用动态规划，通过考虑每个顶点作为中间点来更新任意两点之间的最短路径。其时间复杂度$ \(O(n^3)\) $在处理稠密图时较为适合。

6. 为什么邻接表更适合稀疏图？

• 思考点：
• 邻接表和邻接矩阵各自的空间复杂度与边数$ \(m\) $和顶点数$ \(n\) $之间的关系如何影响它们的选择？
• 提示：
• 邻接矩阵的空间复杂度为$ \(O(n^2)\)$，适合稠密图（边数接近$ \(n^2\)）$。
• 邻接表的空间复杂度为$ \(O(n + m)\)$，在稀疏图中（边数接近$ \(n\)）$节省空间，表现更好。