python - Python,Dijkstra 的算法可视化
问题描述
我正在尝试在 python 中可视化 Dijkstra 的算法,其中每个节点都是一个正方形 - 见下图。但感觉有点不对劲。我将最短路径的结果与标准 A* 进行了比较,但我没有得到完全相同的路径。我认为我的代码已关闭,但我不知道到底如何。
我正在使用优先队列
网格是对象列表的列表 -
每个对象代表屏幕上的一个立方体——
draw - 将网格绘制到屏幕上
** -code- ** 中的代码是我在发布问题后编辑的部分。
def dijkstra_algorithm(grid, start, end):
# set up dist (distance to start) with infinity
dist = {elem: float("inf") for row in grid for elem in row}
# distance from start to start is 0.
dist[start] = 0
# set up prev dict - prev[V] = U - represents that the shortest current path to X is through U
prev = {}
# create Priority Queue based on distance from origin and insert start to PQ
PQ = PriorityQueue()
counter = 0
# create hash table to check if element is inside PQ.
PQ.put((0, counter, start))
PQ_hash = {start}
# insert every elem except start into PQ with distance infinity
for row in grid:
for elem in row:
if elem != start:
PQ.put((dist[elem],**float("inf")**, elem))
PQ_hash.add(elem)
# iterate untill PQ is empty
while not PQ.empty():
current = PQ.get()[1] # get element with min distance - index 1 in (dist[elem], elem)
# if what's left is infinitly far - there is no path from start to end
if dist[current] == float('inf'):
return False
PQ_hash.remove(current) # remove element from Hash table (PQ.get removes elem from PQ)
current.set_closed() #(color - red)
draw_func() #(draw the grid)
if current == end: #end node found
reconstruct_path(prev, current, draw_func) #draw path from end to start
end.set_end()
start.set_start()
return True # found
#iterate over all neighbors of current node
for neighbor in current.neighbors:
# if neighbor inside PQ
if neighbor in PQ_hash:
#calculate distance if we go to neighbor through current (+1 distance)
alt = dist[current] + 1
#if quicker - update
if alt < dist[neighbor]:
dist[neighbor] = alt
prev[neighbor] = current
**counter += 1 **
PQ.put((dist[neighbor],**counter**, neighbor))
neighbor.set_open() #color green
draw_func() #draw the grid
#path not found
return False
我认为这与我添加到 PQ 而不是编辑这一事实有关,但我不确定。另外,我很抱歉缺少 PEP8,我试着在我去的时候评论我的想法,我希望它是可以理解的。
解决方案
为进入 PQ 的元素添加一个计数器可以对所有内容进行分类。PQ.put((0, counter, start)),计数器在程序开始时从零开始,每次我们将一个元素放入PQ(最后一个if语句)中,我们都会增加计数器,从而降低优先级.
推荐阅读
- python-3.x - 如何在 Python 中修复我的不一致 if 语句
- java - 检查此日期是否超过新日期的一分钟
- jquery - 使用 jQuery validate 进行多步表单验证
- c++ - 我可以告诉一个对象删除我吗?
- api - 传递 / 和 -- 在 url 中显示 403 Forbidden Error
- arrays - Perl 范围数组变量 - for 循环
- javascript - 如何从 PHP 获取图像数组到 Javascript
- jmeter-plugins - 如何将 Jmeter 服务器代理与其他应用程序一起使用?
- python - 加载 .npy 文件作为 pytorch 的数据集
- javascript - 计算模拟时钟指针相对于边界框的动态长度