面试：找到几个元素的最短路径

Question

有一个博物馆，组织为 NxN 房间。部分房间已上锁且无法进入。其他房间是开放的，部分房间有警卫。警卫只能在博物馆内向北、南、东、西移动，只能穿过开放的房间。对于每个房间，找到到守卫的最短距离。你的算法的时间复杂度是多少？

Answer 1

首先，考虑一种相对简单的方法。

将每个警卫 G 作为房间集合中的顶点，R=N*N，以及相邻房间（边）之间的可能路径 E。

如果必须知道所有房间的最小距离，则从每个警卫到每个房间的 BFS。

这应该需要时间 G * (R+E)，或类似 G*(N*N+E) 或 G*(N*N)。

这当然可以通过记忆来优化，因为每个 BFS 都会重复计算已经完成的子树。根据房间配置，这可以大大降低上述时间复杂度的 G。然而，我确信一定有比这更好的东西。

Answer 2

图形化解决方案
每个房间都是一个节点
仅门打开的房间之间有边缘
使用Floyd–Warshall算法，然后检查每个房间和每个警卫之间的最小距离

房间数量 - R = N^2

警卫数量 - G

时间复杂度为 O(R^3 +R*G)= O( R^3) = O(N^6)

R^3 对于 Floyd–Warshall

Answer 3

如果我们使用人工源和从源到每个警卫的零长度边来增强博物馆图，则单源最短路径树可通过 BFS（未加权）/Dijkstra（加权）及时计算 Õ(n ² + g)，给出从每个房间到最近的警卫的距离。

Answer 4

以下是 IVlad 和 throtawayacct 提到的最佳解决方案 (O(N^2)) 的摘要。由于某种原因，他们的声音没有被听到:)

将 NxN 网格视为一个图，其中节点代表房间，边缘代表相邻房间之间的门。所有边的权重均为 1。一组节点 U 被标记为“受保护的房间”。

这个想法是使用 BFS 遍历，从连接到所有受保护房间的新节点开始，并从 v0 开始按距离递增的顺序扫描房间。每次访问一个节点时，到达该节点所采取的步数代表了距守卫房间的距离，并且由于路径扩展顺序，保证其最小：

Add an artificial node v0 and connect it to all nodes in U
Create a simple queue Q, that stores pairs <node, dist>
Q.enqueue(<v0, -1>) 
Create a hash set S, that contains all visited nodes
S.add(v0)
while not Q.isEmpty() {
    pathTail := Q.dequeue()
    output distance pathTail.dist for node pathTail.node
    for all neighbours v of pathTail.node
        if not S.contains(v)
            Q.add(<v, pathTail.dist + 1>)

    S.add(pathTail.node)

}

复杂性分析

该图是平面的，所以我们有 |V|+|E|=O(|V|)。因此，这个 BFS 运行时间为 O(|V|)=O(N^2)。

事实上，我们对边的权重是统一的，这让事情变得简单；队列保证具有单调的距离值。以 dijkstra 为例，边的权重可能不同，因此需要优先级队列，这会影响时间复杂度。这里提出的相同问题，如果房间之间的权重不同，则需要 O(NNlog N) 时间。

Answer 5

您只需将该博物馆视为一张图并使用 Dijikstra 算法即可。

wiki 链接

您对给定页面上的复杂性进行了讨论。

Answer 6

您可以在本系列文章中找到 Dijkstra 的最短路径算法：

广度和深度优先搜索

Answer 7

拥有一个队列，其中每个条目都保存一个正方形的地址和一个整数。将所有守卫的位置放入一个队列中，每个守卫都用整数“0”标记。每个方格都应该有容纳数字的空间，并且它们最初都应该是空白的。

然后，只要队列中有东西，就从队列中拉出一个条目，并检查相关方格是否有标记值。如果是这样，则忽略该队列条目并继续下一个队列条目。否则，用队列中的值标记该方格，并将所有可直接到达的相邻方格放入队列中，其值比当前条目的值高一个（因此，当从队列中拉出第一批方格中的每一个时，他们会得到值“1”）。每个方格在为空时只会被访问一次，并且每个被访问的方格最多会导致另外四个方格排队，因此经过队列的物品总数将是方格数量的四倍加上警卫数量。通过在将每个方块添加到队列之前检查它是否为空，可以轻松地将这个值减少一个常数因子；这不会消除所有冗余队列，但会消除一些。

Answer 8

我假设一个函数 edgeCost(i,j) 返回从房间 i 到房间 j 的转换成本（如果没有则无穷大，否则为 1）。另外，edgeCost(i,i) = 0 并且不存在负循环。设 R 为房间数（在您的情况下，R = N^2）：

int path[R][R];
/*
 * Each path[i][j] is initialized to
 * edgeCost(i,j) or infinity if there is no 
 * edge between i and j.
 */

function play():
 for k = 1 to R:
  for i = 1 to R:
   for j = 1 to R:
    path[i][j] = min(path[i][j], path[i][k] + path[k][j]);

或者您可能知道，Floyd-Warshall 算法（所有对最短路径），时间复杂度为 O(|R|^3)。