logo标签列表

Dijkstra算法求最长路径

javaalgorithmcomputer-sciencegraph-algorithmdijkstra
3
编辑2：这可能有点晚了，但我弄清楚了问题所在，是我的问题。我误解了项目，它要求寻找最大带宽路径而不是最长路径。虽然这两者不同，但直到现在我才知道。因此，在任何带宽路径问题中（无论是最大还是最小），权重都不会累加，路径值由路径中最小的权重确定。可以将其想象为一条管道路径，水流量由路径上最细的管道决定。 编辑1：我解决了PQ问题，但仍然没有起作用。
这是一个作业（我承认），但如果我不提交它，我可能会整门课程挂掉。我们应该修改Dijkstra算法以计算最长简单路径，而不是最短路径。我想不出解决方案。我在互联网上搜索并找到了这个（甚至是同样的问题）。
但是当我运行它时，它会产生不正确的值。我是否遗漏了什么？为什么它甚至不将权重与前一个节点相加？为什么使用min？
关于图的信息： 1.我们随机生成图形，使每个节点连接到大约25％的其他节点。 2.权重为正数。 3.图中有25个节点。
问题说：“路由算法是在图中查找最大带宽路径的算法。它基于使用Max-Heap结构修改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);
        }
    }

样例输出: 带宽不是最高的

提前感谢大家。

1
使用此页面上的算法：https://en.wikipedia.org/wiki/Dijkstra's_algorithm#Algorithm，将步骤3更改为始终获取最大距离值而不是最小值。 - Jonathan M
图的大小有多大（节点数量）？ - yassin
1
@yassin 这个图有25个节点。每个节点连接到大约其他节点的25％（不是完全25％）。权重为正数。 - Kh5
1
你应该写代码还是伪代码？你展示了你找到了一些在线资源，并且你说你“运行它”，但你没有展示你具体运行的是什么。如果你不展示你的实现，我们怎么能帮助你呢？请参考[mcve]和[ask]。 - PJvG
1
@Kh5 是的，算了吧。你必须重新考虑那段代码。问题在于：你正在更改已经在优先队列中的元素的比较值，但这不是优先队列的工作方式。你不能修改其中的元素，优先队列不会在每次更改时重新排序它们。 - yassin
显示剩余17条评论
3个回答
3
不能使用Dijkstra算法来找到最长的简单路径。这个问题是NP难问题。实际上，目前没有已知的多项式解决方案。
如果图相对较小，可以使用动态规划来得到一个O(2^n * poly(n))的解决方案，适用于n ~ 20-30（状态为访问过的顶点和最后一个顶点的掩码。如果可能，添加一个顶点作为转换）。
如果图很大，可以使用不同的启发式方法和近似算法，结合局部优化技术来获得一个好的（但不一定是最优的）解决方案。
由于问题要求修改Dijkstra算法：指数级解决方案可能可以通过将路径长度和位掩码插入优先队列来实现。 - yassin
@yassin 我不会称之为修改。在我看来，它看起来像是完全不同的算法。 - kraskevich
0

您无法更改已经在优先队列中的元素。 通常情况下，对于Dijkstra算法，您需要一个减少键函数，但是库中的函数不支持该操作，因此您可以使用不同的BW值多次重新插入节点到优先队列中。类似这样（将其视为伪代码 :))

    PriorityQueue<pair<Node, int>> queue;

    public MaxDijkstra(Graph graph, Node s){

        queue = new PriorityQueue<>(new Comparator<pair<Node, int>>(){
            @Override
            public int compare(pair<Node, int> n1, pair<Node, int> n2) {
                return n1.second > n2.second;
            }
        });

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

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

        while(!queue.isEmpty()){
            pair<Node, int> u = queue.remove();
            if (u.second < u.first.getNodeBW()) continue; //important - skip if you already saw better value
            Iterator<Node> iterator = u.getNeighborNodeIterator();
            while(iterator.hasNext()){
                Node v = iterator.next();
                int min = Integer.min(Utils.getNodeBW(u), Utils.getEdgeBW(u.getEdgeBetween(v)));
                if(min > Utils.getNodeBW(v)){
                    Utils.setNodeBW(v, min);
                    queue.insert({v, min});
                }
            }
        }
    }
}
谢谢，我不知道。我已经绕过它了，我知道这样做不好，只是为了调试。但这仍然不能帮助解决问题。 - Kh5
@Kh5 嗯，我现在唯一的想法是 getEdgeBW 不正确。 - yassin
0
尝试将所有权重都乘以-1，以使所有权重变为负数。然后可以使用弗洛伊德-沃舍尔算法。 弗洛伊德-沃舍尔算法适用于带有负权重的无环图。 因此，使用弗洛伊�-沃舍尔算法找到最短路径，再将其乘以-1，就得到了原始图中的最大路径。
但是我们应该修改Dijkstra算法。我们能否对其使用-1技巧（进行一些修改）？ - Kh5
对不起，我没有仔细阅读你的原始问题。Dijkstra算法不能处理负权重。我的想法只适用于能够处理负权重的算法，比如Floyd-Warshall算法。 - J. Michael Wuerth
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接