4回答

Cooper_s_code

提问者

2020-12-12

老师，对于marked数组标记，您给的答案我又认真思考了下，但是还是感觉在优先队列下可以不需要marked标记，我实现了下：

//Dijkstra
    MinHeap<Edge<Weight>> heap(G.Vertexs());
    from[s] = new Edge<Weight>(s,s,Weight());
    Edge<Weight> e ;
    heap.insrtelement(*from[s]);
    while(!heap.isEmpty()){
        e = heap.extractMin();
        int v = e.W();
        class Graph::adjIterator adj(v,G);
        for(Edge<Weight> *it = adj.begin(); ！adj.end(); it = adj.next() ){
            int w = it->other(v);
          
                if( !from[w] ){
                     from[w] = it;
                     distTo[w] = distTo[v] + it->Wt();
                     heap.insrtelement(*it);
               }
                 else if (distTo[v] + it->Wt() < distTo[w]){
                     from[w] = it;
                     distTo[w] = distTo[v] + it->Wt();
                     heap.insrtelement(*it);
                }

        }
    }

1

11

Cooper_s_code

回复

liuyubobobo

嗯，明白了老师，是考虑的方式不对，谢谢！

2020-12-12

共11条回复

Cooper_s_code

提问者

2020-12-12

并且似乎它对有向图可以允许有负权边，但对于无向图它会不停的向堆中加入这个负权边。

0

1

liuyubobobo

dij 算法是不可以处理包含负权边的图的。

2020-12-12

共1条回复

liuyubobobo

2020-12-09

赞！你是对的，对于使用索引堆来说，其实不需要使用 marked，这也是使用索引堆的一个优势。

但如果只需用普通的优先队列的话，我们其实也能完成 dijkstra 算法。此时，这个 marked 非常重要。因为一个点可能多次被添加到优先队列中。

可以参考这个问答：http://coding.imooc.com/learn/questiondetail/135830.html 

以及我的参考代码的 55-56 行：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/09-Shortest-Path/Course%20Code%20(C%2B%2B)/Optional-1-Dijkstra-based-on-Min-Heap/Dijkstra.h 

继续加油！：）

0

2

Cooper_s_code

发不全，只能写在问题下

2020-12-12

共2条回复

Cooper_s_code

提问者

2020-12-08

感觉应该是没有作用的，我将边0-3权值改为1，将3-4权值改为0.9思考了下，程序考察的结果是0到3再到4然后到2，到2时考察3，不用标记，0到3仍然是最短的，程序不会修改存好的权值，这样看来marked好像真的没起作用，麻烦老师解答下？

0

0