java - Dijkstra 最长路径算法

Question

编辑 2:这可能为时已晚，但我发现了问题所在，是我。我误解了这个项目，它要求最大带宽路径而不是最长路径。这是不同的，但我直到现在才知道。所以基本上在任何带宽路径问题中(无论是最大还是最小)，权重都不累加，路径值由路径中最小的权重决定。将其想象成一条管道路径，水流由路径上最细的管道决定。

编辑 1:我修复了 PQ 问题，但仍然无法正常工作。

这是一个作业(我承认)，但如果我不提交它，我可能会挂掉整个类(class)。我们应该修改 Dijkstra 的算法来计算最长的 SIMPLE 路径而不是最短路径。我想不出解决办法。我在网上搜索了一下，发现this (甚至是同样的问题)。

但是当我运行它时，它产生了不正确的值。有什么我想念的吗？为什么它甚至不将重量与前身相加？为什么要使用 min ？

关于图表的信息: 1. 我们随机生成图，每个节点都连接到 大约 25% 的其他节点。 2.权重为正。 3.图中有25个节点。

问题说“路由算法是在图中寻找最大带宽路径的算法。它基于使用最大堆结构对 Dijkstra 算法的修改”。有什么技巧可以帮助吗？

public class MaxDijkstra {
    Graph graph;
    PriorityQueue<Node> queue;

    public MaxDijkstra(Graph graph, Node s){
        this.graph = graph;
        s.addAttribute("ui.class", "start");
        queue = new PriorityQueue<>(new Comparator<Node>(){
            @Override
            public int compare(Node n1, Node n2) {
                if(Utils.getNodeBW(n1) == Utils.getNodeBW(n2)){
                    return 0;
                }else if(Utils.getNodeBW(n1) < Utils.getNodeBW(n2)){
                    return 1;
                }else{
                    return -1;
                }
            }
        });

        // init
        for(Node n : graph){
            Utils.setNodeBW(n, 0);
        }
        Utils.setNodeBW(s, Float.POSITIVE_INFINITY);

        // add to Q
        for(Node n : graph){
            queue.add(n);
        }

        while(!queue.isEmpty()){
            Node u = queue.remove();
            Iterator<Node> iterator = u.getNeighborNodeIterator();
            while(iterator.hasNext()){
                Node v = iterator.next();
                float min = Float.min(Utils.getNodeBW(u), Utils.getEdgeBW(u.getEdgeBetween(v)));
                if(min > Utils.getNodeBW(v)){
                    Utils.setNodeBW(v, min);
                    Utils.setPreOfNode(v, u);
                }
            }

            // validate PQ
            // I know it is not good, just for debuggin now
            // I will implemnt my own PQ later
            List<Node> list = new ArrayList<>();
            while(!queue.isEmpty()){
                Node w = queue.remove();
                list.add(w);
            }
            for(Node w : list){
                queue.add(w);
            }
        }
    }

    public void printInfo(){
        for(Node n : graph){
            System.out.println("N="+n.getId()+" D="+Utils.getNodeBW(n)+" pre="+ (Utils.getPreOfNode(n) == null ? "NIL" : Utils.getPreOfNode(n).getId()) );
        }
    }

    /**
     * Just to colourise the path
     * @param target 
     */
    public void backtrack(Node target){
        target.addAttribute("ui.class", "end");
        Node currunt = target;
        Node pre = Utils.getPreOfNode(currunt);
        while(pre != null){
            currunt.getEdgeBetween(pre).addAttribute("ui.class", "route");
            currunt = pre;
            pre = Utils.getPreOfNode(currunt);
        }
    }

示例输出:

提前谢谢大家。

Answer 1

您不能使用 Dijkstra 算法来找到最长的简单路径。这个问题是 NP 难的。事实上，没有已知的多项式解决方案。

如果图比较小，可以用动态规划得到一个O(2^n * poly(n))的解，对于n~20-30(状态是访问过的顶点和最后一个顶点的掩码。如果可能的话，过渡是添加一个顶点)。

如果图很大，您可以使用不同的启发式方法和近似值，结合局部优化技术来获得好的(但不一定是最优的)解决方案。