LeetCode 图论 - 全局最短路径问题

在图论中，全局最短路径问题是一个经典问题，它涉及到在图中找到所有顶点对之间的最短路径。下面是一些常用的算法来解决这个问题的介绍。

常见算法

1. Floyd-Warshall 算法

   • 这是一个动态规划算法，可以处理带权图和无权图，它的时间复杂度为 (O(n^3))。
   • Floyd-Warshall 算法详细解析

2. Johnson 算法

   • 当图中包含负权边时，Floyd-Warshall 算法可能不适用，此时可以使用 Johnson 算法，它的时间复杂度为 (O(n^2 \log n))。
   • Johnson 算法详细解析

3. Dijkstra 算法

   • Dijkstra 算法用于单源最短路径问题，即从一个顶点到其他所有顶点的最短路径。对于无权图，可以使用 BFS 算法。
   • Dijkstra 算法详细解析

实例图片

图论算法示例图

总结

全局最短路径问题在图论中非常重要，了解和掌握这些算法对于解决实际问题非常有帮助。希望这篇文章能帮助你更好地理解全局最短路径问题。