package org.xiu68.ch04.ex12;

 public class Ex4_10 {

     public static void main(String[] args) {

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

             {0,10,0,4,1},

             {0,0,0,0,0},

             {0,-10,0,0,0},

             {0,0,0,0,0},

             {0,0,2,0,0}

         };

         MGraph m1=new MGraph(edges);

         m1.bellmanFord(0,2);

     }

 }

 class MGraph{

     private int[][] edges;        //有向图边集

     private int vexNum;            //顶点数目

     private int[] dist;            //源点到该顶点的距离

     private int maxDistant;        //表示距离无穷远

     public MGraph(int[][] edges){

         this.edges=edges;

         this.vexNum=edges.length;

         this.dist=new int[vexNum];

         this.maxDistant=1000000;

     }

     public void bellmanFord(int start,int edgeNum){

         //初始化dist数组

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

                 dist[i]=maxDistant;

         }

         dist[start]=0;

         for(int i=0;i<edgeNum;i++){                //从源点到任何一个顶点的最多edgeNum条边的最短路径

             boolean flag=false;                    //记录在本次循环中从源点到某个顶点是否有更短的路径

             //遍历所有的边

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

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

                     if(edges[j][k]!=0 && dist[k]>dist[j]+edges[j][k]){

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

                         flag=true;

                     }

                 }

             }

             if(flag==false)        //已经求得所有顶点最多edgeNum条边的最短路径

                 break;

         }

         /*

         //本次循环检测是否有负环存在

         //从源点到某个顶点有n条边,且路径更短,说明有负环存在

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

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

                 if(edges[i][j]!=0 && dist[j]>dist[i]+edges[i][j])

                     return false;

             }

         }

         */

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

             System.out.println(i+":"+dist[i]);

     }

 }