Dijkstra的算法-如何使用优先级队列或最小堆？
我一直在努力实现Dijkstra的算法；更具体地，具有优先级队列的部分。将顶点添加到数据结构中，并使用迭代器遍历所有顶点并找到最小距离；这很容易，但这次是。
我想要的是：
-
< li >能够将顶点插入数据结构中 < li >提取(返回并移除)距离dist[v]最小的顶点v
我相信为了让Dijkstra的算法正常工作，你应该能够在恒定时间内插入顶点并在log（n）时间内提取它们；有人建议可以使用优先级队列和最小堆，但对我来说，我们可以保持队列或最小堆有序似乎不现实，因为距离不断被修改。
那么，我应该如何声明和使用优先级队列、最小堆或其他数据结构来实现这一点呢？
共有2个答案
您可以使用一对来存储节点和值（第一个元素应该是值，以便优先级队列与此值进行比较）。维护一个布尔数组access[]，您将在其中指示您是否访问过某个节点（最初都是假的）。
每次你采取优先级队列的前端元素检查你是否访问过这个节点，即检查是否访问[pq.front（）.second] == false。检查其所有相邻边，并添加从此路径到达的节点。如果这是真的，那么你应该忽略它，因为你已经访问了它的长度更少。您添加的边不会超过 E 边，因此时间复杂度保持不变。
你可以通过链接http://community.topcoder.com/tc?module=Static了解更多关于这种方法的信息
-
我的问题是：每个节点的优先级是什么？我认为它是最小值的传入边缘的权重，但我不确定。这是真的吗？ 第二个问题，当我提取队列的根时，如果这个节点不与任何一个被访问的节点邻接，它将如何工作？
-
我在CLRS，第三版（第662页）中读到了Dijkstra的算法。下面是我不明白的书中的一部分： 如果图足够稀疏--特别是-我们可以通过用二进制最小堆实现最小优先级队列来改进算法。 为什么图形应该是稀疏的？ 下面是另一部分：
-
我正在为Dikjstra算法做一个优先级队列。我目前在插入方法上有麻烦。我包含了整个类的代码，以防你需要更好地了解我想完成的事情。我将堆索引放在一个数组列表(heapIndex)中，堆放在另一个数组列表中。 那是我运行程序后的输出(值，优先级，堆索引)。*(-1)表示heapIndex中的空单元格。
-
这是我写的Dijkstra算法的代码: 在这方面我不能理解的工作 这涉及到: < code>()运算符在这里有什么用？我是说它在这段代码中是如何运作的？ 还有为什么我们使用
-
在我实现Dijkstra算法的过程中，我有1个数组（包含所有节点）和1个优先级队列（包含所有节点）。每当一个节点排队时，我都会用新的距离和它来自哪里来更新所有相邻的节点，这样我就可以回溯路径。 优先级队列中的节点更新为新距离，数组中的节点更新为它来自的位置和新距离。当节点出列时，数组中的最终距离会更新： 用前一个节点的信息更新数组和用距离更新优先级队列是否可以接受？ 只要找到更好的距离，就会发生这
-
我正在使用优先级队列实现Dijkstra的算法，我想要一个函数从堆中删除一个元素，但我只能从Dijkstra的主节点索引中向它发送顶点索引，我找不到它在堆上的位置，我负担不起进行二进制搜索。有什么想法吗？