【浙江大学】数据结构，浙大的数据结构讲的很精炼，不枯燥易懂，十分适合数据结构的学习。

以下笔记也是根据以该课程为主，并加以具体实现代码。

Dijkstra算法可以求解单个点到其他点的最短路径，若要求任意两点之间的最短距离，使用Dijkstra算法则显得有些麻烦。为了解决这个问题，我们可以使用Floyd算法。

Floyd算法：Floyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。其时间复杂度为$O(N^3)$（因为代码里面有三个for循环），空间复杂度为$O(N^2)$。

Floyd算法采用了动态规划的思想，当求任意两点i，j的最短路径时有两种可能：

通过将上述两种情况相比较，从而确定i，j两点之间的最短路径。假设图G一共有N个顶点，分别用这N个顶点作为中介点进行路径更新，更新N此后即可求得任意两点之间的最短路径。

在编写代码的时候，我们需要两个N*N的数组dist和path，分别表示i，j两点之间的最短距离，以及i，j两点最短距离所经过的顶点。

关于三个for循环顺序为k，i，j的解释。

* 即，统计图中各个顶点间的最短路径。