public class Vertex implements Comparable<Vertex>{

  /**
   * 節(jié)點名稱(A,B,C,D)
   */
  private String name;
  
  /**
   * 最短路徑長度
   */
  private int path;
  
  /**
   * 節(jié)點是否已經(jīng)出列(是否已經(jīng)處理完畢)
   */
  private boolean isMarked;
  
  public Vertex(String name){
    this.name = name;
    this.path = Integer.MAX_VALUE; //初始設置為無窮大
    this.setMarked(false);
  }
  
  public Vertex(String name, int path){
    this.name = name;
    this.path = path;
    this.setMarked(false);
  }
  
  @Override
  public int compareTo(Vertex o) {
    return o.path > path?-1:1;
  }
}

public class Graph {

  /*
   * 頂點
   */
  private List<Vertex> vertexs;

  /*
   * 邊
   */
  private int[][] edges;

  /*
   * 沒有訪問的頂點
   */
  private Queue<Vertex> unVisited;

  public Graph(List<Vertex> vertexs, int[][] edges) {
    this.vertexs = vertexs;
    this.edges = edges;
    initUnVisited();
  }
  
  /*
   * 搜索各頂點最短路徑
   */
  public void search(){
    while(!unVisited.isEmpty()){
      Vertex vertex = unVisited.element();
      //頂點已經(jīng)計算出最短路徑，設置為"已訪問"
     　　vertex.setMarked(true);  
      //獲取所有"未訪問"的鄰居
      　　List<Vertex> neighbors = getNeighbors(vertex);  
      //更新鄰居的最短路徑
      updatesDistance(vertex, neighbors);    
      pop();
    }
    System.out.println("search over");
  }
  
  /*
   * 更新所有鄰居的最短路徑
   */
  private void updatesDistance(Vertex vertex, List<Vertex> neighbors){
    for(Vertex neighbor: neighbors){
      updateDistance(vertex, neighbor);
    }
  }
  
  /*
   * 更新鄰居的最短路徑
   */
  private void updateDistance(Vertex vertex, Vertex neighbor){
    int distance = getDistance(vertex, neighbor) + vertex.getPath();
    if(distance < neighbor.getPath()){
      neighbor.setPath(distance);
    }
  }

  /*
   * 初始化未訪問頂點集合
   */
  private void initUnVisited() {
    unVisited = new PriorityQueue<Vertex>();
    for (Vertex v : vertexs) {
      unVisited.add(v);
    }
  }

  /*
   * 從未訪問頂點集合中刪除已找到最短路徑的節(jié)點
   */
  private void pop() {
    unVisited.poll();
  }

  /*
   * 獲取頂點到目標頂點的距離
   */
  private int getDistance(Vertex source, Vertex destination) {
    int sourceIndex = vertexs.indexOf(source);
    int destIndex = vertexs.indexOf(destination);
    return edges[sourceIndex][destIndex];
  }

  /*
   * 獲取頂點所有(未訪問的)鄰居
   */
  private List<Vertex> getNeighbors(Vertex v) {
    List<Vertex> neighbors = new ArrayList<Vertex>();
    int position = vertexs.indexOf(v);
    Vertex neighbor = null;
    int distance;
    for (int i = 0; i < vertexs.size(); i++) {
      if (i == position) {
        //頂點本身，跳過
        continue;
      }
      distance = edges[position][i];  //到所有頂點的距離
      if (distance < Integer.MAX_VALUE) {
        //是鄰居(有路徑可達)
        neighbor = getVertex(i);
        if (!neighbor.isMarked()) {
          //如果鄰居沒有訪問過，則加入list;
          neighbors.add(neighbor);
        }
      }
    }
    return neighbors;
  }

  /*
   * 根據(jù)頂點位置獲取頂點
   */
  private Vertex getVertex(int index) {
    return vertexs.get(index);
  }

  /*
   * 打印圖
   */
  public void printGraph() {
    int verNums = vertexs.size();
    for (int row = 0; row < verNums; row++) {
      for (int col = 0; col < verNums; col++) {
        if(Integer.MAX_VALUE == edges[row][col]){
          System.out.print("X");
          System.out.print(" ");
          continue;
        }
        System.out.print(edges[row][col]);
        System.out.print(" ");
      }
      System.out.println();
    }
  }
}

public class Test {

  public static void main(String[] args){
    List<Vertex> vertexs = new ArrayList<Vertex>();
    Vertex a = new Vertex("A", 0);
    Vertex b = new Vertex("B");
    Vertex c = new Vertex("C");
    Vertex d = new Vertex("D");
    Vertex e = new Vertex("E");
    Vertex f = new Vertex("F");
    vertexs.add(a);
    vertexs.add(b);
    vertexs.add(c);
    vertexs.add(d);
    vertexs.add(e);
    vertexs.add(f);
    int[][] edges = {
        {Integer.MAX_VALUE,6,3,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
        {6,Integer.MAX_VALUE,2,5,Integer.MAX_VALUE,Integer.MAX_VALUE},
        {3,2,Integer.MAX_VALUE,3,4,Integer.MAX_VALUE},
        {Integer.MAX_VALUE,5,3,Integer.MAX_VALUE,5,3},
        {Integer.MAX_VALUE,Integer.MAX_VALUE,4,5,Integer.MAX_VALUE,5},
        {Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,3,5,Integer.MAX_VALUE}
    
    };
    Graph graph = new Graph(vertexs, edges);
    graph.printGraph();
    graph.search();
  }
  
}