如果需要重新访问BFS中的访问节点，时间复杂度是多少？ [英] What is the time complexity if it needs to revisit visited nodes in BFS?

问题描述

我正在研究算法问题。

为简化起见，该问题可以简化为：

For Simplification, the problem could be reduced to:

给出一个m * n矩阵，其中有一堆特殊点，在该矩阵中找到从A点到B点的最佳路径。
最佳路径是经过最少特殊点的路径。如果有多条路径的特殊点最少，请选择最短的路径。如果仍然有多个路径，请从中随机选择一个。

Given an m * n matrix, with a bunch of special points, find an optimal path from point A to point B in this matrix. The optimal path is a path which passes fewest special points. If there are multiple paths with fewest special points, choose the shortest one. If there are still multiple paths, select one randomly among them.

BFS肯定可以解决此问题。要排队，请记录每个点的信息。如果找到更好的路径，请更新信息并将此点放入队列。最后在B点输出信息。

This problem could definitely be solved by BFS. To hold a queue, record information of each point. If a better path is found, update information and put this point into the queue. Output information at point B at last.

棘手的是，一个点可能会被多次重访，在这种情况下，我无法估计时间复杂度。有人可以帮我吗？

The tricky part is a point may be revisited multiple times and I cannot estimate the time complexity in this case. Can anyone help me with it?

推荐答案

最终目的是不降低任何特殊点或尽可能减少。您可以通过以下设置为此使用Dijkstra：普通边线成本1.特殊点和所有其他成本之间的边线大于 m * n （因此即使您经历了整个迷宫没有特殊节点，它比走一步要好，但要经过特殊节点）。

The ultimate goal is to not hit any special points or as less as possible. You can use Dijkstra for that with following settings: Ordinary edge costs 1. The edge between special point and all other costs more than m*n (therefore even if you go through the whole maze without special node, its better than go one step, but through special node).

然后您运行Dijsktra，就可以了。由于您的图具有每个节点最大的边缘数量（其矩阵，因此最多4个方向），因此边缘的数量约为4 * m * n，即 O（m * n）。

Then you run Dijsktra and you have it. As you have graph with maximum amount of edges per node (its matrix, so 4 directions at maximum) the number of edges is approximatelly 4*m*n which is O(m*n).

所以您的 V =（m * n）和 E = O（m * n），而Dijkstra是 O（V + E * log E）。只需将其放在此处，您将得到 O（m * n + m * n * log（m * n））= O（m * n * log（m * n））

So your V=(m*n) and E=O(m*n) and Dijkstra is O(V + E*log E). Just put it there and you get O(m*n + m*n * log(m*n)) = O(m*n*log(m*n))

这篇关于如果需要重新访问BFS中的访问节点，时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！