package com.qf.greaph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

/**
 * @author jiayoo
 * 7 / 30 
 * Dijkstra最短路徑算法是一種單源最短路徑
 * 本文采用的是鄰接表表示圖。
 * 
 * 圖的表示： 1. 采用 ArrayList 來儲存 圖的頂點
 *   2. 采用 Map 來儲存 邊集 ， map 可以 實現(xiàn) 一對多的關(guān)系， 因此能很好的實現(xiàn)鄰接表結(jié)構(gòu)
 *   3. 采用ArrayList的原因 是使 邊集有序 這樣， Node 的里面 那個記錄距離的集合才能一一對應(yīng)
 */

public class MinPath {

  private static class graph{
    private ArrayList<Node1> nodes = new ArrayList<>(); // 表示圖頂點 ， 同時他也作為V集合
    private Map<Node1, ArrayList<Node1>> adjaNode = new HashMap<>(); // 表示圖的邊
    private ArrayList<Node1> nodes1 ; // 表示S集合, 即存儲已經(jīng)訪問的節(jié)點，
    private float[] minPath; //用來存儲源點到每個頂點的距離
    float min = Float.MAX_VALUE;

    /**
     * @param start
     * @param end
     * @param distance
     * 構(gòu)建鄰接表。使之成為圖
     */
    public void addAdjaNode(Node1 start, Node1 end, float distance) {

      if (!nodes.contains(start)) {
        nodes.add(start);
      }
      if (!nodes.contains(end)) {
        nodes.add(end);
      }
      if (adjaNode.containsKey(start) && adjaNode.get(start).contains(end)) {
        return ;
      }

      if (adjaNode.containsKey(start)) {
        adjaNode.get(start).add(end);
      }else {
        ArrayList<Node1> node = new ArrayList<Node1>();
        node.add(end);
        adjaNode.put(start, node);
      }
      start.distonext.add(distance);
    }

    /**
     * 將圖打印出來
     */
    public void prinGraph() {
      if (nodes == null || adjaNode == null) {
        System.out.println("圖為空");
        return ;
      }

      for (Entry<Node1, ArrayList<Node1>> entry : adjaNode.entrySet()) {
        System.out.println("頂點 ： " + entry.getKey().name + " 鏈接頂點有： ");
        for(int i = 0; i < entry.getValue().size(); i++) {
          System.out.print(entry.getValue().get(i).name + " " + "距離是： " + entry.getKey().distonext.get(i) + ", ");
        }
        System.out.println();
      }
    }


    /**
     * 1.這個方法用于初始化S集合 及 初始化距離數(shù)組
     * 2. 設(shè)置源點， 并且將源點作為內(nèi)容 初始化算法
     */
    public void findMinPath() {
      Node1 node1 = null; // 用來記錄列表里最小的點
      nodes1 = new ArrayList<>(); // 存儲已經(jīng)遍歷過的點
      minPath = new float[nodes.size()]; // 初始化距離數(shù)組
      int i;
      /*
       * 對最短路徑進(jìn)行初始化， 設(shè)置源點到其他地方的值為無窮大
       * */
      for (i = 0; i < minPath.length; i++) {
        minPath[i] = Float.MAX_VALUE;
      }
      Node1 node = nodes.get(0); 
      nodes1.add(node); // 將源點加入 S 集合
      node.visited = true;

      ArrayList<Node1> n = adjaNode.get(node); // 獲取到源點的邊集
      /*
       * 先對源節(jié)點進(jìn)行初始化
       * 1. 對 距離數(shù)組進(jìn)行初始化。
       * 2. 找到源點到某個距離最短的點， 并標(biāo)記
       * 
       * */
      for (i = 0; i < n.size(); i++) {
        minPath[n.get(i).id] = node.distonext.get(i); // 最短路徑記錄
        if (min > node.distonext.get(i)) {
          min = node.distonext.get(i);
          node1 = n.get(i); // 找到當(dāng)前最短路徑
        }
      }
      this.process(node1, min);
    }


    private void process(Node1 node, float distance ) {
      min = Float.MAX_VALUE; //作為標(biāo)記
      Node1 node1 = null; // 同樣記錄距離最短的點
      int i;
      ArrayList<Node1> n = adjaNode.get(node); // 獲得邊集
      for (i = 0 ; i < n.size(); i++) {
        if (!n.get(i).visited) { // 這個邊集里的頂點不在 S 集合里
          if (minPath[n.get(i).id] == Float.MAX_VALUE) {
            minPath[n.get(i).id] = distance + node.distonext.get(i); // 源點到下一點的距離
          }else if (distance + node.distonext.get(i) < minPath[n.get(i).id] ) { //源點到該頂點的距離變小了， 則改變
            minPath[n.get(i).id] = distance + node.distonext.get(i); // 更新源點到下一個點的距離
          }
        }
      }
      /*
       * 這個for 用于找到 距離集合中 距離源點最近 且并未被訪問過的
       * 這個for 同時可以確保 該節(jié)點確實可到達(dá)
       * */

      for (i = 1; i < minPath.length; i++) {
        if (!nodes.get(i).visited) {
          if (min  > minPath[i] ) { 
            min = minPath[i];
            node1 = nodes.get(i);
          }
        }
      }
      if (node1 != null) {
        node1.visited = true;
        process(node1, min); //源點到 當(dāng)前的距離
      }else { // 說明此位置沒有后續(xù)節(jié)點， 或者 已經(jīng)全部被訪問完了， 則到達(dá)此位置只需要加上此位置的值

      }      
    }
  }

  public static void main(String[] args) {

    Node1 n1 = new Node1(0,"A");
    Node1 n2 = new Node1(1,"B");
    Node1 n3 = new Node1(2,"C");
    Node1 n4 = new Node1(3,"D");
    Node1 n5 = new Node1(4,"E");
    Node1 n6 = new Node1(5,"F");
    graph gp = new graph();
    gp.addAdjaNode(n1, n2, 6);
    gp.addAdjaNode(n2, n1, 6);
    gp.addAdjaNode(n1, n3, 3);
    gp.addAdjaNode(n3, n1, 3);


    gp.addAdjaNode(n2, n3, 2);
    gp.addAdjaNode(n3, n2, 2);
    gp.addAdjaNode(n2, n4, 5);
    gp.addAdjaNode(n4, n2, 5);

    gp.addAdjaNode(n3, n4, 3);
    gp.addAdjaNode(n4, n3, 3);
    gp.addAdjaNode(n3, n5, 4);
    gp.addAdjaNode(n5, n3, 4);

    gp.addAdjaNode(n4, n5, 2);
    gp.addAdjaNode(n5, n4, 2);
    gp.addAdjaNode(n4, n6, 3);
    gp.addAdjaNode(n6, n4, 3);

    gp.addAdjaNode(n5, n6, 5);
    gp.addAdjaNode(n6, n5, 5);

    // 下面嘗試一下非連通圖

//   /**
//    *   權(quán)值： 1
//    *  A -----------B
//    * 權(quán) | *
//    * 值 | *  權(quán)值： 3
//    * 2  |  *
//    *   C-----D
//    * 權(quán)值： 5
//    * 
//    * 
//    * */
//   
//   gp.addAdjaNode(n1, n2, 1);
//   gp.addAdjaNode(n2, n1, 1);
//   
//   gp.addAdjaNode(n1, n3, 2);
//   gp.addAdjaNode(n3, n1, 2);
//   
//   gp.addAdjaNode(n1, n4, 3);
//   gp.addAdjaNode(n4, n1, 3);
//   
//   gp.addAdjaNode(n3, n4, 5);
//   gp.addAdjaNode(n4, n3, 5);
    gp.prinGraph();
    System.out.println("--------------------------------------------------------------------");
    System.out.println("此數(shù)組下標(biāo)代表id，值代表從源點分別到各點的最短距離， A開始的下標(biāo)是0， B、C、D等依次類推， 并且源點默認(rèn)設(shè)置為id為零0的開始");
    gp.findMinPath();  
    System.out.println(Arrays.toString(gp.minPath));

  }

}


/**
 * 頂點類
 */
class Node1{
  String name; 
  boolean visited = false; // 訪問狀態(tài)。有效 減少原算法移除V集合中元素所花費的時間
  int id = -1; // 設(shè)置默認(rèn)id為-1
  ArrayList<Float> distonext = new ArrayList<>(); //這一點 到另外每一個點的距離
  public Node1(int id, String name) {
    this.id = id;
    this.name = name;
  }

}