package 有向网每对顶点的路径Floyd算法;
public class Floyd {
/**
* @param args
*/
private static int max=Integer.MAX_VALUE;
private static int[][]dist=new int[6][6];
private static int[][]prve=new int[6][6];
private static int[][]a={
{max,max,10,max,30,100},
{max,max,5,max,max,max},
{max,max,max,50,max,max},
{max,max,max,max,max,10},
{max,max,max,20,max,60},
{max,max,max,max,max,max}
};
public void floyd(int [][]a,int p[][],int [][]d){
int n=d.length;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
d[i][j]=a[i][j];
if(a[i][j]<Integer.MAX_VALUE)
p[i][j]=j;
else
p[i][j]=-1;
}
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(d[i][j]>d[i][k]+d[k][j]){
d[i][j]=d[i][k]+d[k][j];
p[i][j]=p[i][k];
}
System.out.println("路径 长度");
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
int next=p[i][j];
if(next==-1)
System.out.println(i+" to "+j+" no path.");
else
{
System.out.print("v"+i);
while(next!=j){
System.out.print("-->v"+next);
next=p[next][j];
}
System.out.print("-->v"+j);
}
System.out.print("路径长度是: "+d[i][j]+", ");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Floyd F=new Floyd();
F.floyd(a, prve, dist);
}
}
结果一直是
路径 长度
0 to 0 no path.
路径长度是: -68, 0 to 1 no path.
路径长度是: -136, 0 to 2 no path.
路径长度是: -2147483647, 0 to 3 no path.
路径长度是: -154, 0 to 4 no path.
路径长度是: -46, 0 to 5 no path.
路径长度是: -2147483629, 1 to 0 no path.
路径长度是: -76, 1 to 1 no path.
路径长度是: -36, 1 to 2 no path.
路径长度是: -2147483643, 1 to 3 no path.
路径长度是: -54, 1 to 4 no path.
路径长度是: -2147483635, 1 to 5 no path.
路径长度是: -2147483637, 2 to 0 no path.
路径长度是: -62, 2 to 1 no path.
路径长度是: -54, 2 to 2 no path.
路径长度是: -2147483643, 2 to 3 no path.
路径长度是: -72, 2 to 4 no path.
路径长度是: -2147483623, 2 to 5 no path.
路径长度是: -2147483583, 3 to 0 no path.
路径长度是: -62, 3 to 1 no path.
路径长度是: -54, 3 to 2 no path.
路径长度是: -2147483643, 3 to 3 no path.
路径长度是: -72, 3 to 4 no path.
路径长度是: -2147483623, 3 to 5 no path.
路径长度是: -2147483583, 4 to 0 no path.
路径长度是: -62, 4 to 1 no path.
路径长度是: -90, 4 to 2 no path.
路径长度是: -2147483643, 4 to 3 no path.
路径长度是: -108, 4 to 4 no path.
路径长度是: -2147483623, 4 to 5 no path.
路径长度是: -2147483583, 5 to 0 no path.
路径长度是: -22, 5 to 1 no path.
路径长度是: -90, 5 to 2 no path.
路径长度是: -2147483643, 5 to 3 no path.
路径长度是: -108, 5 to 4 no path.
路径长度是: -2147483623, 5 to 5 no path.
路径长度是: -2147483583,
怎么回事？
矩阵图如下
------解决思路----------------------
因为代码有错误。给你一个正确的实现，自己对照下：
import java.util.ArrayList;
import java.util.List;
public class FloydInGraph {
private static int max=Integer.MAX_VALUE; //dist[i][j]=max<==>i 和 j之间没有边
private int[][] dist; //顶点i 到 j的最短路径长度，初值是i到j的边的权重
private int[][] path;
private List< Integer> result=new ArrayList< Integer>();
public static void main(String[] args) {
FloydInGraph graph=new FloydInGraph(6);
int[][] matrix={
{max,max,10,max,30,100},
{max,max,5,max,max,max},
{max,max,max,50,max,max},
{max,max,max,max,20,10},
{max,max,max,max,max,60},
{max,max,max,max,max,max}
};
for(int i=0;i<6;i++)
for(int j=0;j<6;j++)
{
graph.findCheapestPath(i,j,matrix);
List< Integer> list=graph.result;
System.out.print(i+" to "+j+",the cheapest path is: ");
if(max==graph.dist[i][j])
{
System.out.println("There is no path from "+i+" to "+j);
}
else
{
System.out.println(list.toString());
System.out.println("path distance: "+graph.dist[i][j]);
}
}
}
public void findCheapestPath(int begin,int end,int[][] matrix){
floyd(matrix);
result.clear();
result.add(begin);
findPath(begin,end);
result.add(end);
}
public void findPath(int i,int j){
int k=path[i][j];
if(k==-1)return;
findPath(i,k);
result.add(k);
findPath(k,j);
}
public void floyd(int[][] matrix){
int size=matrix.length;
for(int i=0;i< size;i++){
for(int j=0;j< size;j++){
path[i][j]=-1;
dist[i][j]=matrix[i][j];
}
}
for(int k=0;k< size;k++){
for(int i=0;i< size;i++){
for(int j=0;j< size;j++){
if(dist[i][k]!=max&&
dist[k][j]!=max&&
dist[i][k]+dist[k][j]< dist[i][j]){
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=k;
}
}
}
}
}
public FloydInGraph(int size){
this.path=new int[size][size];
this.dist=new int[size][size];
}
}