为什么要用一个额外的distTo来存权值

来源：9-3 实现Dijkstra算法

易萧

2017-07-16

直接向堆中添加或更新权值不就已经得到了那个权值了么，需要的话直接从堆里取就行了，存到distTo里有什么意义。

补充：在堆中添加一个返回指定索引的值的函数或者重载[ ]运算符岂不美滋滋。

补充2：

其实从ipq.insert( w, distTo[w] )和ipq.change( w, distTo[w] )这两句上可以看到，ipq堆中w位置所存的权值和distTo[w]其实就是一样的，相当于先更新了distTo[w]，再用distTo[w]去更新ipq的w位置。而ipq堆虽然每次popindex()都会删除一个元素，但它并没有真正删除，最新的权值仍然保留在堆的原数组中，动的只是索引。于是我可以在最小索引堆中新添加一个函数来获得相应位置的权值：

template <class Weight>
Weight operator[]( int p ){
    return data[p+1]; //从索引1开始
}

其中的data就是堆存放权值的数组，data[i+1]和distTo[i]很明显就是相等的。所以，同样能从堆中随时返回从起始点到任意点的最短路径，Dijkstra里面的操作也能相应地更新成：

for( tmp=ite.begin() ; !ite.end() ; tmp=ite.next() ){
    v = tmp->other(p);
    if( !visited[v] ){
        if( from[v] == -1 ){
            from[v]=p;
            heap.insert( v, tmp->val() );
        }
        else{
            if( heap[v]>heap[p]+tmp->val() ){
            heap.change( v, heap[p]+tmp->val() );
            from[v]=p;
            }
        }
    }
}

这里就去掉了给distTo[v]赋值，而是直接将值添加或改变到heap中的v位置。

写回答

4回答

liuyubobobo

2017-07-27

已采纳

看到了你的实现。逻辑上是可以的。

但是从算法设计的角度，我个人不推荐，非常容易让代码的阅读者产生混淆。这里主要利用了“索引堆删除元素其实没有实际进行删除”这样的实现细节。但是这是基于我们实现的索引堆的。如果索引堆结构是其他工程师写的，或者系统提供的模块，你是不能保证这个索引堆有这样的性质的。

从阅读者的角度，你的实现是要去访问之前被你的逻辑声称已经“删除”的元素，这种逻辑在代码阅读的过程中会让阅读者很困惑，为什么删除了还要去访问？会花很多精力才能搞明白，其实这个删除是“假”的，而且在整个dij中，恰好每个边进入索引堆一次，所以这样做是work的。这其实增加了算法的理解难度。但是显示的使用另外一个数组存储结果，完全没有这样的麻烦。索引堆和distTo数组各司其职，每一个结构的作用都很清晰。

依然很赞你的思考！

易萧

非常感谢！

2017-07-27

共1条回复

liuyubobobo

2017-07-26

看到了你的补充，我觉得我还是没有特别理解你的意思。Dijkstra算法中的索引堆是一个辅助算法完成的中间数据结构，当算法结束以后，索引堆里已经为空。在算法过程中，将计算的结果使用distTo保存，之后在shortestPathTo方法中，使用O(1)的时间即可随时取出从起始点到任意点的最短距离。

如果你觉得你的想法更优，试试把你的想法用代码表述出来？

易萧

那我再补充一下

2017-07-26