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;
}
}
