marked标记与有向边

Question

1、marked的数组标记作用在这个实例中其实是没有作用的，换句话说maked标记与否对与这个案例都是正确的，是不是案例的问题，还是对于有向边就不用做marked标记？
2、如果标记是有用的，讲解时marked【s】=true；这一句是否多余了？github中Dijkstra.h中的第50行。

Answer 1

提问者 Cooper_s_code 2020-12-12 00:24: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);
                }

        }
    }

• liuyubobobo #1

  这样做算法的复杂度最坏变成了 V * E 级别。因为同一个顶点会被多次加入队列，不使用 mark，就会被重复处理。

• 提问者 Cooper_s_code 回复 liuyubobobo #2

  如果这个算法是正确的，那对于负权边，这个算法似乎可以求解，当一个结点的有负权边时，并且被沿着负权边（负权边从堆顶出来时）再次访问时，他的edgeto会变小，相应的会使他连接的下一个结点的边再次进入堆中，这样似乎比Bellman—Ford算法少访问几个结点。

• liuyubobobo 回复 提问者 Cooper_s_code #3

  当有负权边的时候，dij 算法是错误的。

点开查看后面8条评论

Answer 2

提问者 Cooper_s_code 2020-12-12 00:30:41

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

• liuyubobobo #1

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

Answer 3

liuyubobobo 2020-12-09 11:16:47

赞！你是对的，对于使用索引堆来说，其实不需要使用 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 

继续加油！：）

• 提问者 Cooper_s_code #1

  老师，对于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()

• 提问者 Cooper_s_code #2

  发不全，只能写在问题下

Answer 4

提问者 Cooper_s_code 2020-12-08 22:57:14

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