algorithm - 如何在添加最少数量的新节点的情况下找到图中的最短路径？

Question

我需要在添加的节点数最少的图中找到最短路径。起始节点和结束节点并不重要。如果图中指定的 n 个节点之间没有路径，我可以添加一些节点来完成最短的树，但我想添加尽可能少的新节点。

我可以使用什么算法来解决这个问题？

Answer 1

从起始节点开始。

如果它是目标节点，你就完成了。

检查每个连接的节点，如果它是目标节点。如果为真，你就完成了

检查是否有任何连接的节点连接到目标节点。如果为真，您就完成了。

否则添加一个连接到开始和结束节点的节点。完成。