1、问题引入
带权有向图中单源点的最短路径问题可以用地杰斯特拉算法求解，如果要求解图中每一对顶点之间的最短路径，类似可以想到的方法为：每次以一个顶点为源点，重复执行地杰斯特拉算法算法n次，这样，便可以求得每一对顶点之间的最短路径，总的执行时间为O(n3）。
这里可以采用另外一种求解算法：Floyd算法。
2、Floyd的基本思想为：
从邻接矩阵a开始进行n次迭代，第一次迭代后a[i,j]的值是从vi到vj且中间不经过变化大于1的顶点的最短路径长度；第k次迭代后a[i,j]的值是从vi到vj且中间不经过变化大于k的顶点的最短路径长度 第n次迭代后a[i,j]的值就是从vi到vj的最短路径长度。
3、算法描述：
(1) 用数组d[i][j]来记录i,j之间的最短距离。初始化d[i][j],若i=j则d[i][j]=0,
若i,j之间有边连接则d[i][j]的值为该边的权值，否则d[i][j]的值为max 。 (2) 对所有的k值从1到n，修正任意两点之间的最短距离，计算d[i][k]+d[k][j]的值， 若小于d[i][j],则d[i][j]= d[i][k]+d[k][j]，否则d[i][j]的值不变。4、具体实现：
带权有向图如下：
在b.txt文件中保存的带权有向图的数据为：
其中第一个数据4表述图中有4个节点，其他的四行四列数据表示各个节点之间的路径长度，9999表示两个节点之间不可达。
import java.io.File;import java.io.FileNotFoundException;import java.util.Scanner;public class Floyd { public static int N; public static int[][] f; public static int[][] path; public static void floyd(){ int i,j,k; i = j = k = 0; for(i = 0; i < N; ++i) for(j = 0; j < N; ++j) for(k = 0; k < N; ++k) if(f[i][j] > f[i][k] + f[k][j]){ f[i][j] = f[i][k] + f[k][j]; path[i][j] = k; } print(); } public static void print(){ for(int i = 0; i < N; ++i){ for(int j = 0; j < N; ++j){ printPath(i, j); System.out.print("="+f[i][j]+"\t"); } System.out.println(); } } public static void printPath(int i, int j){ if(i == j || path[i][j] == -1) System.out.print(i+"->"+j); else{ printPath(i,path[i][j]); System.out.print("->"+j); } } public static void main(String[] args) { String p = "d:/b.txt"; try { Scanner s = new Scanner(new File(p)); while(s.hasNext()){ N = s.nextInt(); f = new int[N][N]; path = new int[N][N]; for(int i = 0; i < N; ++i){ for(int j =0; j < N; ++j){ f[i][j] = s.nextInt(); path[i][j] = -1; } } floyd(); } } catch (FileNotFoundException e) { e.printStackTrace(); } }}