根据顶点与源之间的距离对图中的顶点进行排序的算法
根据顶点与源之间的距离对图中的顶点进行排序的算法
提问于 2014-02-12 02:05:14
我有以下来自数据结构课程的问题，我想知道我的解决方案是否正确。
设G(V，E)是一个连通的无向图，使得|V|=m和|E|=n，每个顶点都有其唯一的名字(从1到n)。现在给定一个源顶点S，我需要根据所有顶点与S的距离对它们进行排序，并打印它们。复杂度O(m+n)
我的解决方案(理论上)：
我将基本上使用BFS伪代码，并在while循环的末尾添加以下命令，例如，在将当前顶点'u‘绘制为黑色之前：
入队(Q2，u)。
然后，我将拥有一个可以打印的排序队列Q2。
你认为这是对的吗？非常感谢！
回答 2
Stack Overflow用户
发布于 2014-02-12 02:28:47
如果您的边是成本加权的，那么您将需要使用Dijkstra算法，而不是广度优先。除此之外，是的，这个方法很好。
Stack Overflow用户
发布于 2014-02-12 03:45:00
您所描述的问题已由Dijkstra algorithm解决。它基本上获取最近的尚未访问的节点，并写下到距离它最近的所有节点的距离：
1. start from the source node S
2. add all neighboring nodes into a list, ordered by their distance
and write down the current shortest distance to them
3. pick the closest node N
4. update the distances of all already visited nodes, if a shorter distance
is available to them through N
5. add remaining neighboring nodes into the list
6. eliminate N from the list and repeat from step 3.必须按照从最近到最远的顺序访问节点，这样才不会错过任何可能的最短路径。
实现Dijkstra的挑战是实现优先级前端，它存储节点，按节点到源的距离排序。如果你使用一个简单的列表，你还需要考虑到一个新节点输入到数组中，因为需要找到元素的正确位置。
因此，对基本Dijkstra有多个改进，例如使用Fibonacci heap作为实现优先级队列的结构。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/21709629
复制相关文章
相似问题
腾讯云开发者
