利用Dijkstra算法求顶点v1到其他各顶点的最短路径Java实现

/**
 *作者：魏宝航
 *2020年11月23日,下午15:31
 */
import java.io.IOException;
import java.util.Scanner;
public class MatrixUDG {
   private int mEdgNum;
   private char[] mVexs;
   private int[][] mMatrix;
   private static final int INF = Integer.MAX_VALUE;
   public MatrixUDG(char[] vexs, int[][] matrix) {
      int vlen = vexs.length;
      mVexs = new char[vlen];
      for (int i = 0; i < mVexs.length; i++)
         mVexs[i] = vexs[i];
      mMatrix = new int[vlen][vlen];
      for (int i = 0; i < vlen; i++)
         for (int j = 0; j < vlen; j++)
            mMatrix[i][j] = matrix[i][j];
      mEdgNum = 0;
      for (int i = 0; i < vlen; i++)
         for (int j = i+1; j < vlen; j++)
            if (mMatrix[i][j]!=INF)
               mEdgNum++;
   }
   private int getPosition(char ch) {
      for(int i=0; i<mVexs.length; i++)
         if(mVexs[i]==ch)
            return i;
      return -1;
   }
   public void dijkstra(int vs, int[] prev, int[] dist) {
      boolean[] flag = new boolean[mVexs.length];
      for (int i = 0; i < mVexs.length; i++) {
         flag[i] = false;
         prev[i] = 0;
         dist[i] = mMatrix[vs][i];
      }
      flag[vs] = true;
      dist[vs] = 0;
      int k=0;
      for (int i = 1; i < mVexs.length; i++) {
         int min = INF;
         for (int j = 0; j < mVexs.length; j++) {
            if (flag[j]==false && dist[j]<min) {
               min = dist[j];
               k = j;
            }
         }
         flag[k] = true;
         for (int j = 0; j < mVexs.length; j++) {
            int tmp = (mMatrix[k][j]==INF ? INF : (min + mMatrix[k][j]));
            if (flag[j]==false && (tmp<dist[j]) ) {
               dist[j] = tmp;
               prev[j] = k;
            }
         }
      }
      System.out.printf("dijkstra(%c): \n", mVexs[vs]);
      for (int i=0; i < mVexs.length; i++)
         System.out.printf("  shortest(%c, %c)=%d\n", mVexs[vs], mVexs[i], dist[i]);
   }
   private static class EData {
      char start;
      char end;
      int weight;
      public EData(char start, char end, int weight) {
         this.start = start;
         this.end = end;
         this.weight = weight;
      }
   };
   public static void main(String[] args) {
      char[] vexs = {'1', '2', '3', '4', '5', '6'};
      int matrix[][] = {
             {   0 ,  1 , INF ,  1 , INF,  1},
             {   1 ,  0 ,  1  ,  1 ,  1 , INF},
             {  INF,  1 ,  0  , INF,  1 , INF},
             {   1 ,  1 ,  INF,  0 ,  1 ,  1},
             {  INF,  1 ,  1  ,  1 ,  0 , INF},
             {   1 , INF,  INF,  1 , INF,  0}};
      MatrixUDG pG;
      pG = new MatrixUDG(vexs, matrix);
      int[] prev = new int[pG.mVexs.length];
      int[] dist = new int[pG.mVexs.length];
      pG.dijkstra(0, prev, dist);
   }
}