遍历最小节点数的最短路径算法

Question

我正在寻找Dijkstra的算法实现,它还考虑了遍历的节点数.

我的意思是,典型的Dijkstra算法,考虑连接节点的边的权重,同时计算从节点A到节点B的最短路径.我想在此插入另一个参数.我希望算法能够对遍历的节点数量赋予一些权重.

因此,在某些值下,从A到B计算的最短路径可能不一定是最短路径,而是遍历节点数最少的路径.

有什么想法吗？

干杯,
RD

编辑:
道歉.我应该更好地解释一下.所以,让我们说,从
(A,B)的最短路线是A - > C - > D - > E - > F - > B覆盖总共10个单位
但我希望算法得出路线A - > M - > N - > B共计12个单位.
所以,我想要的是能够对节点数量进行一些权重,而不仅仅是连接节点的距离.

Answer 1

让我演示为所有边添加一个常量值可以改变哪条路线"最短"(边缘的总重量最小).

这是原始图表(三角形):

A-------B
 \  5  /
2 \   / 2
   \ /
    C

从A到B的最短路径是通过C.现在将常数2添加到所有边.最短路径变为从A直接到B的单步(由于我们为使用额外边缘而引入的"惩罚").

请注意,使用的边数(不包括您开始的节点)与访问的节点数相同.