c# - 是否有一种已知的算法可以找到每对之间距离相同的节点之间的最短距离？

Question

换句话说，我想知道是否有一种已知的算法可以找到节点之间从一个节点到另一个节点的最少移动次数。例如，我可能有一棵树

A - B - C - D
 \     /  \
  E - F -  G

我想要从 A 开始的最短路径至 G .那将是 A->B->C->G或 A->E->F->F .

更具体地说，我有一个

var nodes = new List<Node> 

在哪里

class Node
{
    // ... properties

    List<Node> Neighbors;
}

并给出了一些 Node start, end;在 nodes我想找到从 start 开始的最短路径至 end .

我知道我可以使用 Djikstra 的距离算法 1在每个节点之间，但我认为对于这种情况有更好的方法吗？

Answer 1

BFS 遍历是解决这个问题最快的方法，因为它将在线性时间 O(m + n) 内解决问题。

BFS 是一种层序遍历，这意味着它逐层遍历节点:( 首先遍历距离为 1 条边的所有节点，并在遍历 2 条边的距离等等。)。