package org.xiu68.exp.exp4;

 public class Exp4_1 {

     //建立一个从源点S到终点T的多段图，设计一个动态规划算法求出从S到T的最短路径值，并输出相应的最短路径。

     /*

     d[1] = 0

     for j = 2 to n:

     for all <i,j>∈E :

     d[j] = min{ d[i] + wij }

     return d[n]

     */

     public static void main(String[] args) {

         // TODO Auto-generated method stub

         int m=Integer.MAX_VALUE;

         int[][] edges=new int[][]{

             {m,1,2,5,m,m,m,m},

             {m,m,m,m,4,11,m,m},

             {m,m,m,m,9,5,16,m},

             {m,m,m,m,m,m,2,m},

             {m,m,m,m,m,m,m,18},

             {m,m,m,m,m,m,m,13},

             {m,m,m,m,m,m,m,2},

             {m,m,m,m,m,m,m,m},

         };

         MGraph graph1=new MGraph(edges);

         graph1.minMultistageGraphPath(0, 7);

     }

 }

 class MGraph{

     private int[][] edges;        //有向图表示多段图

     private int vexNum;            //顶点数量

     public MGraph(int[][] edges){

         this.edges=edges;

         this.vexNum=edges.length;

     }

     public void minMultistageGraphPath(int start,int end){

         int[] dist=new int[vexNum];        //从源点到该点的路径长度

         dist[start]=0;

         int[] pre=new int[vexNum];        //在最短路径中该点的前一个顶点

         pre[start]=-1;

         for(int j=1;j<vexNum;j++){    

             dist[j]=Integer.MAX_VALUE;

             pre[j]=-1;

             for(int i=0;i<vexNum;i++){

                 if(edges[i][j]!=Integer.MAX_VALUE && dist[j]>dist[i]+edges[i][j]){

                     dist[j]=dist[i]+edges[i][j];

                     pre[j]=i;

                 }

             }

         }

         //打印最短路径

         System.out.println(start+" to "+end+" is "+dist[end]);

         String path=""+end;

         int preVex=pre[end];

         while(preVex!=-1){

             path=preVex+"-->"+path;

             preVex=pre[preVex];

         }

         System.out.println("the path is:"+path);

     }

 }