我需要在图中找到添加节点最少的最短路径。开始和结束节点并不重要。如果图中指定的 n 节点之间没有路径，我可以添加一些节点来完成最短树，但我想添加尽可能少的新节点。
我可以使用什么算法来解决这个问题？
user198041
问问题
480 次
3 回答
1
从起始节点开始。
如果它是目标节点，你就完成了。
检查每个连接的节点，如果它是目标节点。如果是真的，你就完成了
检查是否有任何连接的节点连接到目标节点。如果是真的，你就完成了。
否则添加一个连接到开始和结束节点的节点。完毕。
于 2009-10-28T12:06:13.307 回答
0
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.
于 2009-10-28T12:15:47.300 回答
0
您希望最小化路径中的节点数量（而不是一般算法中的权重总和）。
如果是这种情况，则为所有边分配相等的权重并找到最短路径（使用通用算法）。你会得到你需要的。
如果没有路径，只需将该边添加到图中。
金沙。
PS：如果给每条边赋值1，路径中的节点数就是权重1（不包括源节点和目的节点）
于 2009-10-28T13:04:17.177 回答