對于權重圖的最短路徑查找

對于任何一種圖求最短路徑，我們都需要先求出權重圖的最下生成樹

一、對于權重無向圖

1、Primi算法：我們用edgeTo[]數組來存儲我們最小生成樹的邊，用disTo[]數組來存儲目前節點到最小生成樹最短邊的權重，然後我們引入一個索引最小優先隊列pq，索引為節點索引，值為索引到最小生成樹邊的權重(不知道的可以自行學一下)，用一個布爾類型的數組marked[]來标記節點是否已存入最小生成樹中

第一步、我們将edgeTo[]，disTo[]，marked[]、pq初始化，并且預設将第一個節點放入pq中，并将dirTo[0]節點處的值初始化為0.0，然後周遊代碼如下

private Edge[] edgeTo;
    private double[] disTo;
    private boolean[] marhed;
    private IndexMinPriortyQueue<Double> pq;

    public MinSpanTree(WeightGraph weightGraph){
        edgeTo = new Edge[weightGraph.size()];
        disTo = new double[weightGraph.size()];
        marhed = new boolean[weightGraph.size()];
        pq = new IndexMinPriortyQueue<>(weightGraph.size());
        for (int i = 0; i < marhed.length; i++) {
            marhed[i] = false;
            disTo[i] = Double.MAX_VALUE;
        }
        pq.inster(0,0.0);
        disTo[0] = 0;
        while (pd.size()>0){
            visit(weightGraph,pq.removeMin());
        }

    }           

第二步、周遊pq，将pq值最小的節點删除，并調用visit()方法，将marked[min]設為true表示節點加入了最小生成樹，周遊删除節點的所有邊，如果連接配接的節點沒有進入最小生成樹比較權重進行更新 edgeTo[]、disTo[]，pq的資料，循環直到周遊完每一個節點，代碼如下：

private void visit(WeightGraph weightGraph,int v){
        marhed[v] = true;
        for (Edge edge : weightGraph.getEdges(v)) {
            int other = edge.getOther(v);
            if(!marhed[other]){
                if(edge.getWeight()<disTo[other]){
                    edgeTo[other] = edge;
                    disTo[other] = edge.getWeight();
                    if(pq.contains(other)){
                        pq.set(other,edge.getWeight());
                    }else {
                        pq.inster(other,edge.getWeight());
                    }
                }
            }


        }
}   ``` 
 Primi算法說白了就是，初始化将第一個元素加入最小生成樹中，然後周遊他的邊看看那個邊短，就把另一個元素加入到樹中，并且把目前邊放到edgeTo數組中，更新disTo數組的時候需要比較要更新的值是否比目前值小，一直重複周遊
 ** 2、kruskal算法，與Primi算法思想是想通的，但是這種算法每次周遊的是一條邊如果兩個邊沒在同一個最小生成樹的子樹中我們就将他們兩個合并為同一個子樹，一直周遊到所有節點合并為一個數**
  第一步，我們用一個Queue<Edge> mst隊列來存儲我們最小生成樹中的邊，用一個并查集 UnionFindSets unionFindSets來存儲所有的邊的分組，引入最小優先隊列 MinPriorityQueue<Edge> pq;來存儲所有的邊依次周遊，代碼如下
           

private Queue<Edge> mst
 private UnionFindSets unionFindSets;

private MinPriorityQueue<Edge> pq;
 public MinSpanTreeKruskal(WeightGraph g){
     mst = new LinkedList<>();
     unionFindSets = new UnionFindSets(g.size());
     pq = new MinPriorityQueue<>(g.edgeNum()+1);
     for (Edge edge : g.getAllEdges()) {
         pq.put(edge);
     }
     spanTree();
 }           

第二步、周遊pq中的元素，每次都删除權重最小的邊，判斷目前邊依賴的兩個節點是否為同一組，不是就合并為一組，直到周遊完成，代碼如下
           

private void spanTree(){

while (!pq.isEmpty()){
         Edge temp = pq.removeMin();
         int from = temp.getOne();
         int to = temp.getOther(from);
         if(!unionFindSets.isSameGroup(from,to)){
             mst.offer(temp);
         }

         connect(from,to);
     }           

}

kruskal算法和Primi算法的差別就是 Primi是周遊點找最短的邊進行合并，而krusal算法是周遊最短的邊通過并查集來進行合并，Kruskal算法相對簡單一些并且容易了解，兩個算法都以切分定理為基礎。
###二、對于有向權重圖的最小生成樹

  ** Dijkstra算法，和Primi算法基本一樣，隻不過邊變得有方向了，而且從不同起點出發會有不同的最小生成樹，直接上源碼了，**
           

private DirEdge[] edgeTo;

private double[] dirTo;
private IndexMinPriortyQueue<Double> pq;

public MinPathDijkstra(Digraph digraph,int s){
    edgeTo = new DirEdge[digraph.size()];
    dirTo = new double[digraph.size()];
    pq = new IndexMinPriortyQueue<>(digraph.size()+1);
    for (int i = 0; i < dirTo.length; i++) {
        dirTo[i] = Double.MAX_VALUE;
    }
    dirTo[s] = 0.0;
    pq.inster(s,0.0);
    while (pq.size()>0){
        relax(digraph,pq.removeMin());
    }
}
private void relax(Digraph digraph,int v){
    Queue<DirEdge> dirEdges = digraph.getEdge(v);
    for (DirEdge dirEdge :dirEdges) {
        int to = dirEdge.getTo();
        if(disTo(v)+dirEdge.getWeight()<disTo(to)){
            edgeTo[to] = dirEdge;
            dirTo[to] = disTo(v)+dirEdge.getWeight();
            if(pq.contains(to)){
                pq.set(to,dirTo[to]);
            }else {
                pq.inster(to,dirTo[to]);
            }
        }
    }
}