package sinboy.datastructure;

import java.util.arraylist;

public class dijkstra ...{
    static arraylist<side> map = null;

    static arraylist<integer> redagg = null;

    static arraylist<integer> blueagg = null;

    static side[] parents = null;

    public static void main(string[] args) ...{
        // 初始化顶点集
        int[] nodes = ...{ 0, 1, 3, 2, 4, 5,6 };

        // 初始化有向权重图
        map = new arraylist<side>();
        map.add(new side(0, 1, 10));
        map.add(new side(0, 3, 30));
        map.add(new side(0, 4, 100));
        map.add(new side(1, 2, 50));
        map.add(new side(2, 4, 10));
        map.add(new side(3, 2, 20));
        map.add(new side(3, 4, 60));
        map.add(new side(4, 5, 50));
        map.add(new side(3, 5, 60));
        map.add(new side(5, 6, 10));
        map.add(new side(3, 6, 80)); 

        // 初始化已知最短路径的顶点集，即红点集，只加入顶点0
        redagg = new arraylist<integer>();
        redagg.add(nodes[0]);

        // 初始化未知最短路径的顶点集,即蓝点集
        blueagg = new arraylist<integer>();
        for (int i = 1; i < nodes.length; i++)
            blueagg.add(nodes[i]);

        // 初始化每个顶点在最短路径中的父结点,及它们之间的权重,权重-1表示无连通
        parents = new side[nodes.length];
        parents[0] = new side(-1, nodes[0], 0);
        for (int i = 0; i < blueagg.size(); i++) ...{
            int n = blueagg.get(i);
            parents[i + 1] = new side(nodes[0], n, getweight(nodes[0], n));
        }

        // 找从蓝点集中找出权重最小的那个顶点,并把它加入到红点集中 
        while (blueagg.size() > 0) ...{
            minshortpath msp = getminsidenode();
            if(msp.getweight()==-1)
                msp.outputpath(nodes[0]);
            else
                msp.outputpath();
            
            int node = msp.getlastnode();
            redagg.add(node); 
            // 如果因为加入了新的顶点,而导致蓝点集中的顶点的最短路径减小,则要重要设置
            setweight(node);
        }
 
    }

    /** *//**
     * 得到一个节点的父节点
     * 
     * @param parents
     * @param node
     * @return
     */
    public static int getparent(side[] parents, int node) ...{
        if (parents != null) ...{
            for (side nd : parents) ...{
                if (nd.getnode() == node) ...{
                    return nd.getprenode();
                }
            }
        }
        return -1;
    }

    /** *//**
     * 重新设置蓝点集中剩余节点的最短路径长度
     * 
     * @param prenode
     * @param map
     * @param blueagg
     */
    public static void setweight(int prenode) ...{
        if (map != null && parents != null && blueagg != null) ...{
            for (int node : blueagg) ...{
                minshortpath msp=getminpath(node);
                int w1 = msp.getweight();
                if (w1 == -1)
                    continue;
                for (side n : parents) ...{
                    if (n.getnode() == node) ...{
                        if (n.getweight() == -1 || n.getweight() > w1) ...{
                            n.setweight(w1);
                            n.setprenode(prenode);//重新设置顶点的父顶点
                            break;
                        }
                    }
                }
            }
        }
    }

    /** *//**
     * 得到两点节点之间的权重
     * 
     * @param map
     * @param prenode
     * @param node
     * @return
     */
    public static int getweight(int prenode, int node) ...{
        if (map != null) ...{
            for (side s : map) ...{
                if (s.getprenode() == prenode && s.getnode() == node)
                    return s.getweight();
            }
        }
        return -1;
    }

    /** *//**
     * 从蓝点集合中找出路径最小的那个节点
     * 
     * @param map
     * @param blueagg
     * @return
     */
    public static minshortpath getminsidenode() ...{
        minshortpath minmsp = null;
        if (blueagg.size() > 0) ...{
            int index = 0;
            for (int j = 0; j < blueagg.size(); j++) ...{
                minshortpath msp = getminpath(blueagg.get(j));
                if (minmsp == null || msp.getweight()!=-1 &&  msp.getweight() < minmsp.getweight()) ...{
                    minmsp = msp;
                    index = j;
                }
            }
            blueagg.remove(index);

        }
        return minmsp;
    }

    /** *//**
     * 得到某一节点的最短路径(实际上可能有多条,现在只考虑一条)
     * @param node
     * @return
     */
    public static minshortpath getminpath(int node) ...{
        minshortpath msp = new minshortpath(node);
        if (parents != null && redagg != null) ...{
            for (int i = 0; i < redagg.size(); i++) ...{
                minshortpath tempmsp = new minshortpath(node);
                int parent = redagg.get(i);
                int curnode = node;
                while (parent > -1) ...{
                    int weight = getweight(parent, curnode);
                    if (weight > -1) ...{
                        tempmsp.addnode(parent);
                        tempmsp.addweight(weight);
                        curnode = parent;
                        parent = getparent(parents, parent);
                    } else
                        break;
                }

                if (msp.getweight() == -1 || tempmsp.getweight()!=-1 && msp.getweight() > tempmsp.getweight())
                    msp = tempmsp;
            }
        }

        return msp;
    }
}

/** *//**
 * 图中的有向边，包括节点名及他的一个前向节点名，和它们之间的权重
 * 
 */
class side ...{
    private int prenode; // 前向节点

    private int node;// 后向节点

    private int weight;// 权重

    public side(int prenode, int node, int weight) ...{
        this.prenode = prenode;
        this.node = node;
        this.weight = weight;
    }

    public int getprenode() ...{
        return prenode;
    }

    public void setprenode(int prenode) ...{
        this.prenode = prenode;
    }

    public int getnode() ...{
        return node;
    }

    public void setnode(int node) ...{
        this.node = node;
    }

    public int getweight() ...{
        return weight;
    }

    public void setweight(int weight) ...{
        this.weight = weight;
    }

}

class minshortpath ...{
    private arraylist<integer> nodelist;// 最短路径集

    private int weight;// 最短路径