解释一下All-Pairs Shortest Path

All-Pairs Shortest Path问题是指在一个带权有向图中，求出任意两个节点之间的最短路径。解决这个问题的算法称为All-Pairs Shortest Path算法。

常用的All-Pairs Shortest Path算法有Floyd-Warshall算法和Johnson算法。

Floyd-Warshall算法的基本思想是动态规划。用dist[i][j]表示从节点i到节点j的最短路径长度，用k表示中间节点，则有状态转移方程：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

其中，dist[i][j]的初始值为节点i到节点j的边权，如果i和j之间没有边，则为正无穷。算法的核心是对k从1到n的循环，依次更新dist[i][j]的值，最终得到所有节点之间的最短路径长度。

Floyd-Warshall算法的时间复杂度为O(n^3)，其中n为节点数，主要时间花费在三层循环上，实际应用中可以通过空间换时间的方式优化算法。

Johnson算法的基本思想是通过引入一个虚拟节点，并将其与所有节点之间的边权设为0，将问题转化为带权有向图中的单源最短路径问题。然后使用Bellman-Ford算法求出虚拟节点到其它所有节点的最短路径长度，再用求最短路径时的松弛操作更新所有边的边权，将问题转化为带权有向图中的多源最短路径问题。最后使用Dijkstra算法求出所有节点之间的最短路径长度。

Johnson算法的时间复杂度为O(n^2logn+m)，其中n为节点数，m为边数，主要时间花费在Bellman-Ford算法和Dijkstra算法上，实际应用中可以通过优化数据结构等方式优化算法。