如果需要重新访问 BFS 中访问过的节点，时间复杂度是多少？
What is the time complexity if it needs to revisit visited nodes in BFS?
我正在研究一道算法题。
为了简化，问题可以简化为：
给定一个m * n矩阵，有一堆特殊点，在这个矩阵中找到从A点到B点的最优路径。
最优路径是经过最少特殊点的路径。如果有多条特殊点最少的路径，则选择最短的一条。如果还有多条路径，select其中随机一条。
这个问题完全可以用BFS来解决。要保持队列，记录每个点的信息。如果找到更好的路径，则更新信息并将该点放入队列中。最后在B点输出信息
棘手的部分是一个点可能会被多次重新访问，我无法估计这种情况下的时间复杂度。有人可以帮我吗？
最终目标是不打任何特殊点或尽可能少。您可以通过以下设置使用 Dijkstra： 普通边缘成本 1. 特殊点与所有其他成本之间的边缘超过 m*n（因此，即使您在没有特殊节点的情况下穿过整个迷宫，也比走一个更好步骤，但通过特殊节点）。
然后你 运行 Dijsktra 你就拥有了。由于每个节点的边数最多（其矩阵，因此最多有 4 个方向），因此边数约为 4*m*n，即 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))
我正在研究一道算法题。
为了简化，问题可以简化为：
给定一个m * n矩阵，有一堆特殊点，在这个矩阵中找到从A点到B点的最优路径。 最优路径是经过最少特殊点的路径。如果有多条特殊点最少的路径，则选择最短的一条。如果还有多条路径，select其中随机一条。
这个问题完全可以用BFS来解决。要保持队列，记录每个点的信息。如果找到更好的路径，则更新信息并将该点放入队列中。最后在B点输出信息
棘手的部分是一个点可能会被多次重新访问，我无法估计这种情况下的时间复杂度。有人可以帮我吗？
最终目标是不打任何特殊点或尽可能少。您可以通过以下设置使用 Dijkstra： 普通边缘成本 1. 特殊点与所有其他成本之间的边缘超过 m*n（因此，即使您在没有特殊节点的情况下穿过整个迷宫，也比走一个更好步骤，但通过特殊节点）。
然后你 运行 Dijsktra 你就拥有了。由于每个节点的边数最多（其矩阵，因此最多有 4 个方向），因此边数约为 4*m*n，即 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))