对于加权图的最短路径查找

我们需要先求出加权图的最下生成树

一、对于加权无向图

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]);
                }
            }
        }
    }