如何在添加最少数量的新节点的情况下找到图中的最短路径？
我需要找到图中添加节点数最少的最短路径。起始节点和结束节点并不重要。如果图中指定的 n 节点之间没有路径，我可以添加一些节点来完成最短的树，但我想添加尽可能少的新节点。
我可以使用什么算法来解决这个问题？
I need to find the shortest path in a graph with the least number of added nodes. The start and end nodes are not important. If there is no path in a graph just between specified n-nodes, I can add some nodes to complete the shortest tree but I want to add as few new nodes as possible.
What algorithm can I use to solve this problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
从起始节点开始。
如果是目标节点，则完成。
检查每个连接的节点是否是目标节点。如果为 true，则完成
检查是否有任何已连接的节点已连接到目标节点。如果是真的你就完成了。
否则添加一个连接到起始节点和结束节点的节点。完毕。
Start with the start node.
if it is the target node, you are done.
Check every connected node, if it is the target node. If true you are done
Check if any of the connected nodes is connected to the target node. If true you are done.
Else add a node that is connected to start and end node. done.
我建议你使用遗传算法。更多信息此处和此处。
快速解释一下，GA 是一种寻找优化和搜索问题的精确或近似解的算法。
您创建可能解决方案的初始群体。您可以使用适应度函数来评估它们，以便找出哪些是最合适的。之后，您将使用进化算法，该算法使用受进化生物学启发的技术，例如继承、突变、选择和交叉。
经过几代之后，您将找到最合适（阅读最短）的问题解决方案。
I recommend you to use genetic algorithm. More information here and here.
Quickly explaining it, GA is an algorithm to find exact or approximate solutions to optimization and search problems.
You create initial population of possible solutions. You evaluate them with fitness function in order to find out, which of them are most suitable. After that, you use evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover.
After several generations, you'll find the most suitable (read shortest) solution to the problem.
您希望最小化路径中的节点数量（而不是像一般算法中的权重总和）。
如果是这种情况，请为所有边分配相同的权重并找到最短路径（使用通用算法）。你将会得到你所需要的。
如果没有路径，只需将该边添加到图中即可。
金沙。
PS：如果为每条边赋予值1，则路径中的节点数将为权重1（不包括源节点和目标节点）
You want to minimize the number of nodes in the path (instead of the sum-of-weight as in general algorithms).
If that is the case, assign equal weight to all the edges and find the shortest path (using the generic algorithms). You will have what you needed.
And if there is no path, just add that edge to the graph.
Sands.
PS: If you give a value of 1 for each edge, the number of nodes in the path would be the weight-1 (excluding the source and destination nodes)