dijkstra/prim 的算法...有一点帮助吗？
我想知道 dijkstra 和 prim 的算法，当他们在多个顶点之间进行选择时会发生什么，并且有多个顶点具有相同的权重。
例如
I was wondering for dijkstra's and prim's algorithm, what happens when they are choosing between more than one vertex to go to ,and there are more than one vertex with the same weight.
For example
Example Image http://img688.imageshack.us/img688/7613/exampleu.jpg
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
没关系。通常，平局会以某种任意方式打破，例如哪个节点首先添加到优先级队列中。
Dijkstra 的目标是找到一条最短路径。如果您想找到所有最短路径，那么您就必须担心联系问题。
It doesn't matter. Usually the tie will be broken in some arbitrary way like which node was added to the priority queue first.
The goal of Dijkstra is to find a shortest path. If you wanted to find all shortest paths, you would then have to worry about ties.
可能有多个 MST，无论您使用哪种任意平局规则，都可能会给出不同的 MST，但它仍然是一个 MST。
例如，您可以想象一个三角形 ABC，其中所有边权重均为 1。本例中共有 3 个 MST，而且都是最小的。
Dijkstra 和最短路径生成树也是如此——可能有多个最短路径生成树。
There could be multiple MSTs, and whichever arbitrary tiebreaking rules you use might give you a different one, but it'll still be a MST.
For example, you can imagine a triangle A-B-C where all the edge weights are one. There are three MST in this case, and they are all minimum.
The same goes for Dijkstra and the shortest path spanning tree -- there could be multiple shortest path spanning trees.
如果我错了，请纠正我，但你的图表没有任何可供应用 Dijkstra 算法的替代路径。
Correct me if I'm wrong, but your graph doesn't have any alternate paths for Dijkstra's algorithm to apply.
Dijkstra 算法以最小的成本扩展（或“放松”）来自触摸但未扩展的节点（或“灰色”节点）的所有边。
如果两个节点具有相同的成本，那么......这只是随机的:)
Dijkstra algorithms expands (or "relaxes") all the edges from a touches but not expanded node (or "gray" node) with the smallest cost.
If two nodes have the same cost, well... it's just random :)