我想知道 dijkstra 和 prim 的算法，当他们在多个顶点之间进行选择时会发生什么，并且有多个顶点具有相同的权重。
例如
问问题
4357 次
4 回答
4
没关系。通常，平局会以某种任意方式被打破，比如哪个节点首先被添加到优先级队列中。
Dijkstra 的目标是找到一条最短路径。如果您想找到所有最短路径，那么您将不得不担心关系。
于 2010-04-28T15:26:49.157 回答
4
可能有多个 MST，您使用的任意决胜规则可能会给您一个不同的规则，但它仍然是 MST。
例如，您可以想象一个三角形 ABC，其中所有边的权重都是 1。在这种情况下，有三个 MST，它们都是最小的。
Dijkstra 和最短路径生成树也是如此——可能有多个最短路径生成树。
于 2010-04-28T15:28:42.433 回答
0
如果我错了，请纠正我，但您的图表没有任何可供 Dijkstra 算法应用的替代路径。
于 2010-04-28T15:27:43.570 回答
-1
Dijkstra 算法以最小的成本扩展（或“放松”）触摸的所有边缘，但不扩展节点（或“灰色”节点）。
如果两个节点的成本相同，那么……这只是随机的 :)
于 2010-04-28T15:27:58.433 回答