求全局最短路径

Question

本帖最后由 wawfully 于 2014-10-10 18:38:16 编辑

Answer 1

下面代码改编自http://blog.csdn.net/a9529lty/article/details/4047319
去掉B1至C1的边，运行结果：
[A1,A2]:1.0
[A1,A2,A3]:2.0
[A1,A2,B3]:2.0
[A1,A2,A3,A4]:3.0
[A1,A2,B3,B2]:3.0
[A1,A2,A3,B4]:3.0
[A1,A2,B3,C4]:3.0
[A1,A2,A3,A4,A5]:4.0
[A1,A2,B3,B2,B1]:4.0
[A1,A2,A3,B4,B5]:4.0
[C1,A1]:-1.0
[C2,A1]:-1.0
[A1,A2,B3,C4,C3]:4.0
[A1,A2,B3,C4,C5]:4.0
保留B1至C1的边，运行结果：
[A1,A2]:1.0
[A1,A2,A3]:2.0
[A1,A2,B3]:2.0
[A1,A2,A3,A4]:3.0
[A1,A2,B3,B2]:3.0
[A1,A2,A3,B4]:3.0
[A1,A2,B3,C4]:3.0
[A1,A2,A3,A4,A5]:4.0
[A1,A2,B3,B2,B1]:4.0
[A1,A2,A3,B4,B5]:4.0
[A1,A2,B3,C4,C3]:4.0
[A1,A2,B3,C4,C5]:4.0
[A1,A2,B3,B2,B1,C1]:5.0
[A1,A2,B3,C4,C3,C2]:5.0
为什么去掉B1至C1的边，[C1,A1]和[C2,A1]就不连通了，[B3,C4]的边也可以使[C1,A1]、[C2,A1]连通啊？B1至C1边的连通的代码是下面两行：
 // map.add(new Side("B1", "C1", 1));
 // map.add(new Side("C1", "B1", 1));
完整代码：import java.util.ArrayList;public class Dijkstra2 {
    static ArrayList<Side> map = null;
    static ArrayList<String> redAgg = null;
    static ArrayList<String> blueAgg = null;
    static Side[] parents = null;    public static void main(String[] args) {
        // 初始化顶点集
        String[] nodes = { "A1", "A2", "A3", "A4", "A5", "B1", "B2", "B3", "B4", "B5", "C1", "C2", "C3", "C4", "C5" };        // 初始化有向权重图
        map = new ArrayList<Side>();
        map.add(new Side("A1", "A2", 1));
        map.add(new Side("A2", "A1", 1));
        map.add(new Side("A2", "A3", 1));
        map.add(new Side("A3", "A2", 1));
        map.add(new Side("A3", "A4", 1));
        map.add(new Side("A4", "A3", 1));
        map.add(new Side("A4", "A5", 1));
        map.add(new Side("A5", "A4", 1));        map.add(new Side("B1", "B2", 1));
        map.add(new Side("B2", "B1", 1));
        map.add(new Side("B2", "B3", 1));
        map.add(new Side("B3", "B2", 1));
        map.add(new Side("B3", "B4", 1));
        map.add(new Side("B4", "B3", 1));
        map.add(new Side("B4", "B5", 1));
        map.add(new Side("B5", "B4", 1));        map.add(new Side("C1", "C2", 1));
        map.add(new Side("C2", "C1", 1));
        map.add(new Side("C2", "C3", 1));
        map.add(new Side("C3", "C2", 1));
        map.add(new Side("C3", "C4", 1));
        map.add(new Side("C4", "C3", 1));
        map.add(new Side("C4", "C5", 1));
        map.add(new Side("C5", "C4", 1));        map.add(new Side("A2", "B3", 1));
        map.add(new Side("B3", "A2", 1));        map.add(new Side("A3", "B4", 1));
        map.add(new Side("B4", "A3", 1));        map.add(new Side("B3", "C4", 1));
        map.add(new Side("C4", "B3", 1));        // map.add(new Side("B1", "C1", 1));
        // map.add(new Side("C1", "B1", 1));        // 初始化已知最短路径的顶点集，即红点集，只加入顶点0
        redAgg = new ArrayList<String>();
        redAgg.add(nodes[0]);        // 初始化未知最短路径的顶点集,即蓝点集
        blueAgg = new ArrayList<String>();
        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++) {
            String 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();
            String node = msp.getLastNode();
            redAgg.add(node);            // 如果因为加入了新的顶点,而导致蓝点集中的顶点的最短路径减小,则要重要设置
            setWeight(node);
        }
    }    /** */
    /**
     * 得到一个节点的父节点
     * 
     * @param parents
     * @param node
     * @return
     */
    public static String getParent(Side[] parents, String 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(String preNode) {
        if (map != null && parents != null && blueAgg != null) {
            for (String node : blueAgg) {
                MinShortPath msp = getMinPath(node);
                float 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 float getWeight(String preNode, String node) {
        if (map != null) {
            for (Side s : map) {
                if (s.getPreNode().equals(preNode) && s.getNode().equals(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(String node) {
        MinShortPath msp = new MinShortPath(node);
        if (parents != null && redAgg != null) {
            for (int i = 0; i < redAgg.size(); i++) {
                MinShortPath tempMsp = new MinShortPath(node);
                String parent = redAgg.get(i);
                String curNode = node;
                while (!"-1".equals(parent)) {
                    float 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 String preNode; // 前向节点    private String node;// 后向节点    private float weight;// 权重    public Side(String preNode, String node, float weight) {
        this.preNode = preNode;
        this.node = node;
        this.weight = weight;
    }    public String getPreNode() {
        return preNode;
    }    public void setPreNode(String preNode) {
        this.preNode = preNode;
    }    public String getNode() {
        return node;
    }    public void setNode(String node) {
        this.node = node;
    }    public float getWeight() {
        return weight;
    }    public void setWeight(float weight) {
        this.weight = weight;
    }
}class MinShortPath {
    private ArrayList<String> nodeList;// 最短路径集    private float weight;// 最短路径    public MinShortPath(String node) {
        nodeList = new ArrayList<String>();
        nodeList.add(node);
        weight = -1;
    }    public ArrayList<String> getNodeList() {
        return nodeList;
    }    public void setNodeList(ArrayList<String> nodeList) {
        this.nodeList = nodeList;
    }    public void addNode(String node) {
        if (nodeList == null)
            nodeList = new ArrayList<String>();
        nodeList.add(0, node);
    }    public String getLastNode() {
        int size = nodeList.size();
        return nodeList.get(size - 1);
    }    public float getWeight() {
        return weight;
    }    public void setWeight(float weight) {
        this.weight = weight;
    }    public void outputPath() {
        outputPath("-1");
    }    public void outputPath(String srcNode) {
        String result = "[";
        if (!"-1".equals(srcNode))
            nodeList.add(srcNode);
        for (int i = 0; i < nodeList.size(); i++) {
            result += "" + nodeList.get(i);
            if (i < nodeList.size() - 1)
                result += ",";
        }
        result += "]:" + weight;
        System.out.println(result);
    }    public void addWeight(float w) {
        if (weight == -1)
            weight = w;
        else
            weight += w;
    }
}