java实现弗洛伊德算法 经典

import java.util.*; class node { int arcs[][]=new int[20][20]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点和边数 } public class a { public static int MAX=1000,num=20; public static boolean P[][][]; //存放每对顶点的最短路径 public static int D[][]; public static node s; public static int []jieguo; public static Vector path; public static void main(String []args) { a b=new a(); s=new node(); P=new boolean[20][20][20]; D=new int[20][20]; jieguo=new int[90]; path = new Vector(); //System.out.println(D[1][2]); a.CreateGraph(s); a.ShortestPath_Floyd(s,P,D); a.Print_ShortestPath(s,P,D); Vector llll=new Vector(); llll = a.Print_OnePath(2,9,10,P); System.out.println(); for(int i=0;i<(llll.size()-1);i++) { //System.out.println(); System.out.print(llll.elementAt(i)+"->"); } System.out.print(llll.elementAt(llll.size()-1)); System.out.println(); //System.out.println(jieguo[3]); //System.out.println(s.arcs[1][2]); } /* floyd.CreateGraph(s); floyd.ShortestPath_Floyd(s,P,D); //利用弗洛依德算法求最短路径 floyd.Print_ShortestPath(s,P,D); //显示每对顶点之间的最短路径*/ public static void CreateGraph(node G) {//构造邻接矩阵结构的图G //Scanner in = new Scanner(System.in); int i,j; //int start,end,weight; //System.out.println("请输入顶点和弧的数目，格式：顶点数，弧数"); G.vexnum=10; //输入图的顶点数和边数 G.arcnum=11; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=MAX; //初始化邻接矩阵 //System.out.println("请输入各条弧和其权值，格式：弧尾，弧头，权值："); G.arcs[1][2]=20; G.arcs[1][3]=10; G.arcs[1][8]=40; G.arcs[2][4]=20; G.arcs[3][4]=20; G.arcs[3][6]=90; G.arcs[3][5]=30; G.arcs[5][8]=30; G.arcs[6][7]=10; G.arcs[7][9]=10; G.arcs[9][10]=40; G.arcs[2][1]=20; G.arcs[3][1]=10; G.arcs[8][1]=40; G.arcs[4][2]=20; G.arcs[4][3]=20; G.arcs[6][3]=90; G.arcs[5][3]=30; G.arcs[8][5]=30; G.arcs[7][6]=10; G.arcs[9][7]=10; G.arcs[10][9]=40; } public static void ShortestPath_Floyd(node G,boolean P[][][],int D[][]) { //用弗洛依德算法求有向网G的每对顶点v和w之间的最短路径P[v][w] //及其带权路径长度D[v][w], //若P[v][w][u]为True,表明u是从v到w当前求得最短路径上的顶点 int u,v,w,i; for(v=1;v<=G.vexnum;v++) //各对顶点之间的初始已知路径及距离 for(w=1;w<=G.vexnum;w++) {D[v][w]=G.arcs[v][w]; for(u=1;u<=G.vexnum;u++) P[v][w][u]=false; if(D[v][w]<MAX) //从v到w有直接路径 {P[v][w][v]=true;P[v][w][w]=true;} } for(u=1;u<=G.vexnum;u++) for(v=1;v<=G.vexnum;v++) for(w=1;w<=G.vexnum;w++) if(D[v][u]+D[u][w]<D[v][w]&&v!=w) //从v经u到w的一条路径更短 { D[v][w]=D[v][u]+D[u][w]; for(i=1;i<=G.vexnum;i++) if(P[v][u][i]||P[u][w][i]) P[v][w][i]=true; } } public static void Print_ShortestPath(node G,boolean P[][][],int D[][]) {//显示每对顶点之间的最短路径及距离 int v,w,j=0; a aaa=new a(); System.out.println("最短路径："); for(v=1;v<=G.vexnum;v++) for(w=1;w<=G.vexnum;w++) if(D[v][w]<MAX) //顶点v和w之间有通路 { //System.out.print(D[v][w]+" "); //从v到w的最短距离 aaa.jieguo[j]=D[v][w]; //System.out.println(j); //System.out.print(aaa.jieguo[j]+" "); j++; //Print_OnePath(v,w,G.vexnum,P); //显示从v到w的最短路径 } for(int i=0;i<=89;i++) { System.out.print(aaa.jieguo[i]+" "); } //return aaa.jieguo; } /*public static void Print_OnePath(int v,int w,int n,boolean P[][][]) {//显示从v到w的最短路径 int i; for(i=1;i<=n;i++) if(i!=v&&i!=w&&P[v][w][i]==true) break; if(i>n) System.out.println(v+"-> "+w); //说明从v到w不需经过其它的顶点 else {Print_OnePath(v,i,n,P); //否则从v到w需经过顶点i，先显示从v到i的最短路径 if(i<10) System.out.print("\b"); //控制显示格式，消除多余的"->" else {} Print_OnePath(i,w,n,P); //显示从i到w的最短路径 } }*/ public static Vector Print_OnePath(int v,int w,int n,boolean P[][][]) {//显示从v到w的最短路径 int i; for(i=1;i<=n;i++) if(i!=v&&i!=w&&P[v][w][i]==true) break; if(i>n) //说明从v到w不需经过其它的顶点 { if(!path.contains(v)) { path.add(v); } if(!path.contains(w)) { path.add(w); } } else {Print_OnePath(v,i,n,P); //否则从v到w需经过顶点i，先显示从v到i的最短路径 if(i<10) System.out.print("\b"); //控制显示格式，消除多余的"->" else {} Print_OnePath(i,w,n,P); //显示从i到w的最短路径 } return path; } }