算法设计最优、最有效的解

Question

我有一个小问题要解决。我很乐意想出最优的解决方案，我认为递归可能是这里最好的选择。如果你认为我的解决方案是理想的，或者你认为有更好的方法，请告诉我。

问题是:我有一个城市清单。我想要的算法是确定一个城市来自华盛顿特区多少度。每个城市都有一张通过它的高速公路的清单。如果一个城市与华盛顿特区共享任何高速公路，那么它离它只有1度。如果一个城市不与华盛顿特区共享一条高速公路，而是与一个距离华盛顿特区1度的城市共享一条高速公路，那么该城市就在2度之外，其子。

我正在考虑建立一个公路清单，每条公路都应该有一个清单，列出所有经过的城市。然后我遍历所有穿过华盛顿特区的高速公路，每一条高速公路，我查看所有经过的城市，然后递归地检查每一个城市，看看最终有一条高速公路能到达华盛顿特区，这样我就能得到学位数。

你会如何处理这个问题？

Answer 1

你会想要构造一个图，其中节点是城市，在城市A和B之间有一个无向边当且仅当有一条连接A和B的公路。那么这个程度就是各个城市之间最短路径的长度(所有的边都有长度1)。你可以用广度第一搜索找到这个。

如何枚举边缘？对于每条公路，只需使用两个嵌套循环来查找所有城市对。

Answer 2

它是经典的最短路径问题(维基)。

城市是顶点，他们之间的高速公路-边缘，数度-最短的道路从城市到华盛顿特区。