logo标签列表

迪杰斯特拉/普里姆算法...需要一点帮助吗？

algorithmdijkstraprims-algorithm
5
4个回答
4

没关系。通常情况下，打破平局的方法是看哪个节点先被添加到优先队列中。

Dijkstra算法的目标是找到一条最短路径。如果您想找到所有最短路径，那么您就需要考虑如何解决平局。

从顶点a开始，假设它刚刚更新了b和c，首先它会到达顶点c，然后更新顶点d和顶点e的权重。现在顶点e的权重为5，顶点b的权重也是5。那么它如何选择下一个要去哪个顶点呢？mathmike，你是说这是随机的吗？谢谢。 - bfpri
是的，它基本上是随机的。 - mathmike
“随机”可能不是您在计算机科学环境中想使用的词-通常意味着“掷骰子”的随机。您在此允许的选择是“任意的” - 任何可能的选择相等值的方法都可以。 - Keith Randall
4

可能会有多个最小生成树，无论您使用任何随意的决策规则，都可能得到不同的结果，但仍将是一个最小生成树。

例如，您可以想象一个三角形A-B-C，其中所有边缘权重都是1。在这种情况下，有三个最小生成树，并且它们都是最小的。

对于Dijkstra和最短路径生成树也是如此--可能会有多个最短路径生成树。

从顶点a开始，假设它刚刚更新了b和c，首先它会前往顶点c，然后更新顶点d和顶点e的权重。现在顶点e的权重为5，顶点b的权重也是5。那么它如何选择下一个要前往的顶点？mathmike，你是说这是随机的吗？谢谢。 - bfpri
我不是数学家Mike，但我认为这并不重要，所以如果你愿意，可以随机生成。 - Larry
2
它并不是真正意义上的“随机”，而是你编程所设定的——有时候以最小索引或最短边长度来决断。这取决于实现方式。 - Larry
0

如果我错了，请纠正我，但是你的图没有任何可供Dijkstra算法应用的备选路径。

是的，Prim算法不适用，但Dijkstra算法可能适用。从顶点a开始，假设它刚刚更新了b和c，首先会到达顶点c，然后更新顶点d和e的权重。现在顶点e的权重为5，顶点b的权重也是5。那么它如何选择下一个要去的顶点呢？mathmike，你是说这是随机的吗？谢谢。 - bfpri
-1
Dijkstra算法会扩展（或“放松”）所有从一个已触及但未扩展的节点（或“灰色”节点）出发、具有最小成本的边。
如果两个节点具有相同的成本，那么...就只是随机的 :)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接