一种具有最少遍历节点数的最短路径算法 [英] A Shortest Path Algorithm With Minimum Number Of Nodes Traversed

问题描述

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

I am looking for a Dijkstra's algorithm implementation, that also takes into consideration the number of nodes traversed.

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

What I mean is, a typical Dijkstra's algorithm, takes into consideration the weight of the edges connecting the nodes, while calculating the shortest route from node A to node B. I want to insert another parameter into this. I want the algorithm to give some weightage to the number of nodes traversed, as well.

所以从A到B计算的最短路径，在一定的值下，不一定是最短路径，而是经过节点数最少的路径.

So that the shortest route computed from A to B, under certain values, may not necessarily be the Shortest Route, but the route with the least number of nodes traversed.

对此有什么想法吗?

干杯，
研发

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

Edit :
My apologies. I should have explained better. So, lets say, the shortest route from
(A, B) is A -> C -> D -> E -> F -> B covering a total of 10 units
But I want the algorithm to come up with the route A -> M -> N -> B covering a total of 12 units.
So, what I want, is to be able to give some weightage to the number of nodes as well, not just the distance of the connected nodes.

推荐答案

让我证明给所有边添加一个常数值可以改变哪条路线是最短的"(边的总权重最小).

Let me demonstrate that adding a constant value to all edges can change which route is "shortest" (least total weight of edges).

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

Here's the original graph (a triangle):

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

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

Shortest path from A to B is via C. Now add constant 2 to all edges. The shortest path becomes instead the single step from A directly to B (owing to "penalty" we've introduced for using additional edges).

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

Note that the number of edges used is (excluding the node you start from) the same as the number of nodes visited.

这篇关于一种具有最少遍历节点数的最短路径算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！