public class Dijsktra {

     public static void main(String[] args)

     {

         Dijsktra d=new Dijsktra();

         int[][] w={{0,1},{2,0}};

         int[] a=d.DijsktraWay(w,0);

         //System.out.println(1111);

     }

     // 返回来的是路径

     public int[] DijsktraWay(int[][] weight, int start) {

         // 接受一个有向图的权重矩阵和一个起点编号start从0编号顶点存在数组中

         // 返回一个int[] 数组表示从start到它的最短路径长度

         int n = weight.length; // 顶点个数

         int[] shortPath = new int[n]; // 存放从start到其他各点的最短路径

         String[] path = new String[n]; // 存放从start到其他各点的最短路径的字符串表示

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

             path[i] = new String(start + ">" + i);

             shortPath[i] = Integer.MAX_VALUE / 2;

         }

         int[] visited = new int[n]; // 标记当前该顶点的最短路径是否已经求出,1表示已求出

         // 初始化第一个顶点求出

         shortPath[start] = 0;//没有环

         visited[start] = 1; // 表示已经访问过

         for (int count = 1; count <= n - 1; count++) // 要加入n-1个顶点，每次加入一个点后

             //就会有一个点被标记

         {

             int k = -1; // 选出一个距离初始顶点start最近的未标记顶点

             int dmin = Integer.MAX_VALUE / 2;

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

                 //如果此点未访问并且距离起始点距离较上一个的小，则应进行修改

                 if (visited[i] == 0 && weight[start][i] < dmin) {

                     dmin = weight[start][i];//表示距离起始点最近的点

                     k = i;//将距离起始点最近的点标记为k

                 }

             }

             if (k == -1) {

                 break;

                 // return null;

             }

             // 将新选出的顶点标记为已求出最短路径且到start的最短路径就是dmin

             shortPath[k] = dmin;

             visited[k] = 1;

             // 以k为中间点修正从start到未访问各点的距离

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

                 if (visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]) {

                     weight[start][i] = weight[start][k] + weight[k][i];

                     path[i] = path[k] + ">" + i;

                 }

                 //System.out.println(shortPath[i]);

                 System.out.println( path[i]);

             }

         }

         return shortPath;

     }

 }