数据结构重读 – 所有点对最短路径(Floyd算法)

如果我们要求每一顶点对之间的最短路径,怎么做呢?

方法1:对N个顶点,依次执行前面的Prim算法。

方法2:使用Floyd算法。

实际上,Floyd算法是动态规划(DP)算法。

原理很简单,我们假设dp[i][j]表示从顶点i到顶点j的最短路径,则dp[i][j] = min (dp[i][k]+dp[k][j], 0<=k<=nvexs)。

于是算法如下:

关于图的读取和创建,我们借用之前Prim算法的Graph类,如下:

测试图:

测试输入:

输出:

Leave a Reply

Your email address will not be published.