algorithm - 到多个潜在目的地之一的最短距离

Question

我在一项编程测试中被要求解决一个问题，在这个问题中我必须找到从矩形图上的每个节点到图中一组可能目的地之一的最短距离。我能够创建一个通过所有测试的解决方案，但我相当确定那里有更高效的算法。

C11--C12--C13--C14
 |    |    |    |
FGB--C22--C23--C24
 |    |    |    |
C31--C32--C33--C34
 |    |    |    |
C41--FGB--C43--C44
 |    |    |    |
C51--C52--C53--C54
 |    |    |    |
C61--C62--C63--FGB

例如，在上图中，假设每个“FGB”代表一个五个人(因为它很好吃)。每个“Cxx”代表一个客户。它本质上是，“每个顾客离最近的五个人有多远？”所以 C11 距离为 1，C12 距离为 2，等等。所有边的权重都为 1。

是Floyd-Warshall我在找什么？我真的不关心所有的配对。

您有什么想法或引用资料可以指给我看吗？非常感谢。

Answer 1

有一个简单的解决方案，分两次通过。

第一遍是向前，一行一行。对于每个节点，您逐步评估到上面左侧最近目标的距离。

D(node)= if target node => 0 else min(D(left neighbor) + 1, D(top neighbor) + 1)

第二遍向后。最终距离评估为

D(node)= min(D(node), D(right neighbor) + 1, D(bottom neighbor) + 1)

记录新值的同时，可以记录对应目标的位置。

(当邻居不存在时，距离按照惯例是无限的。)