我必须计算从n个凝视节点到n个末端节点的最短距离。我不在乎实际路径。节点数远大于n。每个节点正好连接到9个节点。节点到节点的距离是1。我最好的主意是为起始节点做一个Breadth-first search，如果我理解正确的话，它将在线性时间内给我n个末端节点的距离，而我将为每个起始节点做一次。
是否有更快的方法？
这被称为全对最短路径问题。
一般问题（当边缘权重不一定都等于1时）由Floyd-Warshall算法解决，该算法运行时间为O(V^3)。
但是由于我们知道您的图仅具有单位边缘权重，因此我们可以利用这一事实，而可以从每个V起始节点中进行广度优先搜索。由于广度优先搜索在邻接列表上以O(V + E)时间运行，因此该算法的整体运行时间为O(V^2 + VE)。