python - Dijkstra 在 python 中的算法实现跟踪
问题描述
我正在尝试使用优先级队列跟踪 Dijkstra 算法的 python 实现,但我无法遵循,因为我是 python 新手
这是实现
def dijkstra(edges, f, t):
g = defaultdict(set)
for l,r,c in edges:
g[l].add((c,r))
g[r].add((c, l))
q, seen, = [(0,f,())], set(),
while q:
(weight, v1, path) = heappop(q)
if v1 not in seen:
seen.add(v1)
path += (v1,)
if v1 == t:
return weight, path
for k, v2 in g.get(v1, ()):
if v2 not in seen:
heappush(q, (weight+ k, v2, path))
return float("inf")
- 首先为什么它使用
g = defaultdict(set)
而不是g = defaultdict(list)
使用 .add() 而不是 .append() - 我知道在 Dijkstra 算法开始时,您需要将所有节点的所有权重设置为无穷大,但我在这里看不到。
- 节点在哪条线上决定它要经过的路径,就像在哪条线上做出向左或向右的决定一样。简而言之,在代码中节点之间的加权线是在哪里制作的。
解释代码的每一行发生了什么的注释对我理解它真的很有帮助。
解决方案
至于你的问题:
首先为什么它使用
g = defaultdict(set)
而不是g = defaultdict(list)
和使用.add()
而不是.append()
它与list
. 当然,要使用的方法(add
或append
)来自此选择。我能看到的唯一优势是set
您可以避免两次添加相同的边缘。一般来说,一个图可以在相同的两个顶点之间有多个边,它们甚至可以具有相同的权重:当这种情况发生时,没有理由单独考虑这些重复的边,并且set
会确保忽略重复的边。
我知道在 Dijkstra 算法开始时,您需要将所有节点的所有权重设置为无穷大,但我在这里看不到。
有不同的方法来实现算法。实际上,您可以在一开始就将所有顶点添加到优先级队列中,其中除了源顶点之外的所有顶点都以无穷大的权重开始。但是从队列中排除那些“无穷大”顶点会更有效一些:这样队列大小会更小,并且添加到队列中的第一个顶点会稍微快一些。因此,任何不在队列中的顶点实际上都是一个仍然具有无穷大权重的顶点。
节点在哪条线上决定它要经过的路径,就像在哪条线上做出向左或向右的决定一样。简而言之,在代码中节点之间的加权线是在哪里制作的。
代码中没有可见的决定。在找到目标节点之前,所有路径都是潜在的赢家。在此之前,所有已构建的部分路径都在堆上,而堆的特性决定了哪条路径将是下一条将扩展到相邻节点的路径。然后那些较长的路径(具有更多顶点)将再次被扔进堆中,堆的魔力将再次发挥作用。因此,如果您寻找“决定”,则只有在堆内做出决定:它告诉我们哪条路径是堆中存在的权重最小的路径。因此主循环可能在一条路径上工作一点(以扩展它),但在下一次迭代中它可能在完全不同的路径上工作。就这样继续下去,直到突然发现它已经到达了目标顶点。
如果您想了解更多关于 and 的隐藏魔力heappop
,heappush
请阅读有关该主题的Wikipedia 文章。
不是最优的
虽然算法是正确的,但它不是一个有效的实现。以下语句为要复制的路径提供案例,并且该路径可能有多达n 个元素,因此它在一次执行时具有O(n)的最坏情况时间复杂度,从而使算法的最坏情况时间复杂度为O( n²logn) :
path += (v1,)
为了避免这种情况,通常不跟踪整个路径,而只存储对我们形成的前一个节点的反向引用。然后当我们到达目标节点的时候,我们可以沿着这些反向引用走回去并且只构建一次路径。由于存储反向引用需要固定时间,因此这种改进将使算法的时间复杂度为O(nlogn)。
推荐阅读
- build - Can someone expand what is meant by 'configure' and 'build' with CMake files
- docker - 如何使用用户命名空间在 Docker 容器中切换用户
- db2 - 将表格数据转换为饼图数据
- r - R:更改 data.frame 的单个值返回无效因子级别警告
- python - How to remove duplicate elements of, list of dictionaries in python
- reactjs - Getting this error for my App.js file in expo tab application
- c# - 构建 NuGet 包以容纳 3rd 方 DLL 的最佳实践
- c# - 如何在 C# 中正确执行 SQL 脚本并在失败时回滚?
- google-cloud-platform - How to expose a API that is running in a Pod and limit access?
- azure - Azure ARM - 如何通过 ARM 模板部署具有自定义 DNS 服务器的虚拟网络?