是否有一种已知的算法来找到每对之间距离相同的节点之间的最短距离

本文关键字：之间 距离 短距离 节点 一种 算法 是否 | 更新日期: 2023-09-27 18:08:50

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

这样的树
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;
}

并且给定nodes中的Node start, end;，我想找到从start到end的最短路径。

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

是否有一种已知的算法来找到每对之间距离相同的节点之间的最短距离

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

BFS是一个级序遍历意味着它逐级遍历节点:(首先遍历距离为1条边的所有节点，遍历距离为2条边的所有节点，以此类推。)。

距离为1或BFS的Dijkstra -两者都可以应用。众所周知，这类问题可以通过这两种方法来解决。我认为没有更好的办法了。

相关文章：