import java.util.Vector;
import java.util.Stack;

// Dijkstra算法求最短路径
public class Dijkstra<Weight extends Number & Comparable> {

    private WeightedGraph G;      // 图的引用
    private int s;               // 起始点
    private Number[] distTo;    // distTo[i]存储从起始点s到i的最短路径长度
    private boolean[] marked;  // 标记数组,在算法运行过程中标记节点i是否被访问
    private Edge<Weight>[] from; // from[i]记录最短路径中,到达i节点的边是哪一条,可以用来恢复整个最短路径

    //构造函数,使用Dijkstra算法求最短路径
    public Dijkstra(WeightedGraph graph, int s){

        //算法初始化
        G = graph;
        if(s < 0 || s > G.V()){
            throw  new IllegalArgumentException("s is out of bounds!");
        }
        this.s = s;
        distTo = new Number[G.V()];
        marked = new boolean[G.V()];
        from = new Edge[G.V()];
        for (int i = 0 ; i < G.V() ; i ++) {
            distTo[i] = 0.0;
            marked[i] = false;
            from[i] = null;
        }

        // 使用索引堆记录当前找到的到达每个顶点的最短距离
        IndexMinHeap<Weight> ipq = new IndexMinHeap<Weight>(G.V());

        //对于起始点s进行初始化
        distTo[s] = 0.0;
        from[s] = new Edge<Weight>(s, s, (Weight)(Number)0.0);
        ipq.insert(s,(Weight)distTo[s]);
        marked[s] = true;

        while (!ipq.isEmpty()){
            int v = ipq.extractMinIndex();

            // distTo[v]就是s到v的距离
            marked[v] = true;

            // 对v的所有相邻节点进行更新,即松弛操作
            for( Object item : G.adj(v) ){
                Edge<Weight> e = (Edge<Weight>) item;
                int w = e.other(v);
                //如果从s点到w点的最短路径还没有找到
                if( !marked[w] ){
                    //如果w点以前没有访问过
                    //或者访问过,但是通过当前的v点到w点距离更短,则进行更新
                    if( from[w] == null || distTo[v].doubleValue() + e.wt().doubleValue() < distTo[w].doubleValue() ){
                        //长度更新为较小的值
                        distTo[w] = distTo[v].doubleValue() + e.wt().doubleValue();
                        //对from进行更新
                        from[w] = e;
                        //对最小索引堆进行判断
                        if( ipq.contain(w) ){
                            ipq.change(w,(Weight)distTo[w]);
                        }
                        else{
                            ipq.insert(w,(Weight)distTo[w]);
                        }
                    }
                }
            }
        }
    }

    // 返回从s点到w点的最短路径长度
    Number shortestPathTo( int w ){
        if(w < 0 || w >= G.V() ){
            throw new IllegalArgumentException("w is out of bounds!");
        }
        if(!hasPathTo(w)){
            throw new IllegalArgumentException("these two have no path!");
        }
        return distTo[w];
    }

    //判断从s点到w点是否联通
    boolean hasPathTo( int w ){
        if(w < 0 || w >= G.V() ){
            throw new IllegalArgumentException("w is out of bounds!");
        }
        return marked[w];
    }

    //寻找从s到w的最短路径,将整个路径经过的边存放在vec中
    Vector<Edge<Weight>> shortestPath( int w ){
        if(w < 0 || w >= G.V() ){
            throw new IllegalArgumentException("w is out of bounds!");
        }
        if(!hasPathTo(w)){
            throw new IllegalArgumentException("these two have no path!");
        }

        //通过from数组逆向查找到从s到w的路径,存放到栈中
        Stack<Edge<Weight>> s = new Stack<>();
        Edge<Weight> e = from[w];
        while( e.v() != this.s ){
            s.push(e);
            e = from[e.v()];
        }
        s.push(e);

        //从栈中依次取出元素,获得顺序的从s到w的路径
        Vector<Edge<Weight>> res = new Vector<>();
        while (!s.empty()){
            e = s.pop();
            res.add(e);
        }

        return res;
    }

    //打印出从s点到w点的路径
    void showPath(int w){
        if(w < 0 || w >= G.V() ){
            throw new IllegalArgumentException("w is out of bounds!");
        }
        if(!hasPathTo(w)){
            throw new IllegalArgumentException("these two have no path!");
        }

        Vector<Edge<Weight>> path = shortestPath(w);
        for (int i = 0 ; i < path.size(); i ++){
            System.out.print(path.elementAt(i).v() + "->");
            if( i == path.size() - 1)
                System.out.println(path.elementAt(i).w());
        }
    }
}

public class Main {

    // 测试Dijkstra最短路径算法
    public static void main(String[] args) {

        String filename = "testG1.txt";
        int V = 5;

        SparseWeightedGraph<Integer> g = new SparseWeightedGraph<Integer>(V, true);
        // Dijkstra最短路径算法同样适用于有向图
        //SparseGraph<int> g = SparseGraph<int>(V, false);
        ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);

        System.out.println("Test Dijkstra:\n");
        Dijkstra<Integer> dij = new Dijkstra<Integer>(g,0);
        for( int i = 1 ; i < V ; i ++ ){
            if(dij.hasPathTo(i)) {
                System.out.println("Shortest Path to " + i + " : " + dij.shortestPathTo(i));
                dij.showPath(i);
            }
            else
                System.out.println("No Path to " + i );

            System.out.println("----------");
        }

    }
}

import java.util.Vector;
import java.util.Stack;

// 使用BellmanFord算法求最短路径
public class BellmanFord<Weight extends Number & Comparable> {

    private WeightedGraph G;    //图的引用
    private int s;             //设置起始点
    private Number[] distTo;   //distT[i]存放从起始点s到i的最短路径长度
    Edge<Weight>[] from;        //from[i]记录最短路径中,到达i点的边是哪一条
                                 //可以用来回复整个最短路径
    boolean hasNegativeCycle;  //标记图中是否有负权环

    //构造函数,使用BellanFord算法求最短路径
    public BellmanFord(WeightedGraph graph, int s){
        G = graph;
        this.s = s;
        distTo = new Number[G.V()];
        from = new Edge[G.V()];
        //初始化所有的节点s都不可达,由from数组来表示
        for(int i = 0 ; i < G.V() ; i ++){
            from[i] = null;
        }

        //设置distTo[s]=0 ,并且让from[s]不为NULL,表示初始s节点可达且距离为0
        distTo[s] = 0.0;
        from[s] = new Edge<Weight>(s,s,(Weight)(Number)0.0);

        //Bellman-Ford过程
        //进行V-1次循环,每一次循环求出从起点到其余所有点,最多使用pass步可以到达的最短距离
        for( int pass = 1 ; pass < G.V() ; pass ++){

            //每次循环中对所有的边进行一遍松弛操作
            //遍历所有边的方式是先遍历所有的顶点,然后遍历和所有顶点相邻的所有边
            for( int i = 0 ; i < G.V() ; i ++){
                //使用临边迭代器遍历和所有顶点相邻的所有边
                for( Object item : G.adj(i) ){
                    Edge<Weight> e = (Edge<Weight>) item;
                    //对于每一个边首先判断e.v()可达
                    //之后看如果e.w()以前没有到达过,显然可以更新distTo[e.w()]
                    //或者e.w()以前虽然到达过,但是通过这个e可以获得一个更短的距离,即可以进行一次松弛操作,也可以更新distTo[e.w()]
                    if(from[e.v()] != null && (from[e.w()] == null || distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue()) ){
                        distTo[e.w()] = distTo[e.v()].doubleValue() + e.wt().doubleValue();
                        from[e.w()] = e;
                    }
                }
            }

            hasNegativeCycle = detectNegativeCycle();
        }
    }

    //判断图中是否有负权环
    boolean detectNegativeCycle() {
        for(int i = 0 ; i < G.V() ; i ++){
            for(Object item : G.adj(i) ){
                Edge<Weight> e = (Edge<Weight>)item;
                if( from[e.v()] != null && distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue())
                    return true;
            }
        }
        return false;
    }

    //返回图中是否有负权环
    boolean negativeCycle() {
        return hasNegativeCycle;
    }

    //返回从s点到w点的最短路径长度
    Number shortestPathTo(int w){
        if(w < 0 || w >= G.V()){
            throw new IllegalArgumentException("w is out of bounds!");
        }
        if (hasNegativeCycle){
            throw new IllegalArgumentException("this Graph hasNegativeCycle!");
        }
        if(!hasPathTo(w)){
            throw new IllegalArgumentException(s + "to "+ w +"doesn't have path!");
        }
        return distTo[w];
    }

    //判断s点到w点是否联通
    boolean hasPathTo(int w){
        if(w < 0 || w >= G.V()){
            throw new IllegalArgumentException("w is out of bounds!");
        }
        return from[w] != null;
    }

    //寻找s点到w点的最短路径,将整个路径经过的边存放在vec中
    Vector<Edge<Weight>> shortestPath(int w){
        if(w < 0 || w >= G.V()){
            throw new IllegalArgumentException("w is out of bounds!");
        }
        if (hasNegativeCycle){
            throw new IllegalArgumentException("this Graph hasNegativeCycle!");
        }
        if(!hasPathTo(w)){
            throw new IllegalArgumentException(s + "to "+ w +"doesn't have path!");
        }

        //通过from数组逆向查找到从s到w的路径,存放到栈中
        Stack<Edge<Weight>> s = new Stack<>();
        Edge<Weight> e = from[w];
        while (e.v() != this.s){
            s.push(e);
            e = from[e.v()];
        }
        s.push(e);

        //从栈中依次取出元素,获得顺序的从s到w的路径
        Vector<Edge<Weight>> res = new Vector<>();
        while (!s.empty()){
            e = s.pop();
            res.add(e);
        }

        return res;
    }

    //打印出从s点到w点的路径
    void showPath(int w) {
        if(w < 0 || w >= G.V()){
            throw new IllegalArgumentException("w is out of bounds!");
        }
        if (hasNegativeCycle){
            throw new IllegalArgumentException("this Graph hasNegativeCycle!");
        }
        if(!hasPathTo(w)){
            throw new IllegalArgumentException(s + "to "+ w +"doesn't have path!");
        }

        Vector<Edge<Weight>> res = shortestPath(w);
        for(int i = 0 ; i < res.size() ; i ++){
            System.out.print(res.elementAt(i).v() + " -> ");
            if( i == res.size() - 1 ){
                System.out.println(res.elementAt(i).w());
            }
        }
    }
}

public class Main {

    // 测试我们的Bellman-Ford最短路径算法
    public static void main(String[] args) {

        String filename = "testG2.txt";
//        String filename = "testG_negative_circle.txt";
        int V = 5;

        SparseWeightedGraph<Integer> g = new SparseWeightedGraph<Integer>(V, true);
        ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);

        System.out.println("Test Bellman-Ford:\n");

        int s = 0;
        BellmanFord<Integer> bellmanFord = new BellmanFord<Integer>(g, s);
        if( bellmanFord.negativeCycle() )
            System.out.println("The graph contain negative cycle!");
        else
            for( int i = 0 ; i < V ; i ++ ){
                if(i == s)
                    continue;

                if(bellmanFord.hasPathTo(i)) {
                    System.out.println("Shortest Path to " + i + " : " + bellmanFord.shortestPathTo(i));
                    bellmanFord.showPath(i);
                }
                else
                    System.out.println("No Path to " + i );

            System.out.println("----------");
        }

    }
}