如果我们要求每一顶点对之间的最短路径，怎么做呢？
方法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)。
于是算法如下：
import java.util.LinkedList;
public class Fl[......]
数据结构重读 - 所有点对最短路径(Floyd算法)
Leave a reply