有向循环图怎么会有"furthest node"？

Question

我不熟悉算法和图形。我正在尝试解决在线网站上的图问题和查找可达节点数（我认为使用 DFS 可以计算）和从给定源到循环有向图中最远节点的最短路径所需的问题。如果图形可以循环，我无法理解最远节点的含义。这里是什么意思？

Answer 1

即使图是循环的，节点之间的最短路径也永远不会包含同一个节点两次，否则它显然不会是最短的。所以循环的存在真的没有那么重要。

现在，当您查看从源节点（“可达节点”）可以到达的所有节点，以及从源节点到每个节点的最短路径时他们，你将在这些最短路径中有一个 longest（或几个，当它们具有相同的最长长度时）。那些最长的路径通向“最远的节点”。