方法1：直接将单源最短路算法调用V遍
方法2：Floyd算法
T=O(|V|^3)——对于稠密图效果好Floyd算法
Dk[i][j]=路径{i——>{l<=k}——>j}的最小长度D0，D1，...，D|v|-1[i][j]即给出了i到j的真正最短距离最初D-1是什么？邻接矩阵即可 有邻接边定义为权重无邻接边定义为inf 当Dk-1已经完成，递推到Dk时： k不在最短路径{i——>{l<=k]——>j}，则Dk=Dk-1k在最短路径{i——>{l<=k]——>j}，则该路径必定由两段最短路径组成：Dk[i][j]=Dk-1[i][k]+Dk-1[k][j] void Floyd() { for (i=0;i<N;i++) for (j=0;j<N;j++) { D[i][j]=G[i][j]; path[i][j]=-1; } for (k=0;k<N;k++) for (i=0;i<N;i++) for (j=0;j<N;j++) if (D[i][k]+D[k][j]<D[i][j]) { D[i][j]=D[i][k]+D[k][j]; path[i][j]=k; } }
