利用堆场法和预场法

Question

我有以下任务，但我不知道怎么做？

通过Dijkstra计算(字典)从V1节点到其他节点的最短路径。请写出当前堆和相应的Pred-字段.从ExtractMin调用之前的新堆和pred字段开始。

​

​

我通过Dijkstra获得了这个结果，但是应该如何将它添加到min堆(tree)中呢？

​

​

Answer 1

我在一次用于学习算法的旧考试中发现了这个任务。我不知道如何解决这个问题，所以我搜索了几本关于min堆和Dijkstra是如何工作的解释，但是没有找到任何解释。最后我想明白了。因此，我希望这有助于理解如何解决这个问题。

• 步骤1:按字典顺序绘制堆: V1 ->根，然后从左到右绘制其他节点。V1的值为0，所有其他节点inf。
• 步骤2: ExtractMin()：交换根(它的值最低)与最后一个节点并将其切断。
• 步骤3:松弛:如果值减少，更新节点的新值。“从开始到X，当我遍历节点时，我刚刚提取了什么新值，尊重它的前身?它比旧值小吗，然后更新。”
• 步骤4:如果有更好的路径，更新前面的字段。
• 步骤5:调用Heapify()：调用堆，使值最低的节点变为根。
• 重复步骤2至5，直到没有节点为止。

。