我试图解决一个迷宫的问题,在这个问题上,我必须把所有的硬币都放在一个2D网格中,然后用宽度优先搜索来打印最短的路径。该算法在查找路径时标记为已访问的节点(单元),但此问题需要多次访问这些单元,因此我不能将它们标记为已访问。
这是基于ICS 161的BFS的基本伪码。
unmark all vertices
choose some starting vertex x
mark x
list L = x
tree T = x
while L nonempty
choose some vertex v from front of list
vi
我正在研究单源最短路径问题,我对bfs做了一个修改,可以解决这个问题。这个算法的运行时间是O(2E)次,我就是不明白为什么它是错的(否则dijstra的算法肯定不是最有效的算法)。 def bfs_modified(G,src,des):
intialize d(src)=0, and d(!src) = inf
visited[all_vertex]=False
q=queue(src)
while q is not empty:
u=q.pop()
if(not visited[u]):
visi