最小遍数节点数的最短路径算法 [英] A Shortest Path Algorithm With Minimum Number Of Nodes Traversed

问题描述

我的意思是，一个典型的Dijkstra算法，考虑到了Dijkstra算法的实现，它也考虑了遍历的节点数量。考虑连接节点的边的权重，同时计算从节点A到节点B的最短路由。我想在此插入另一个参数。我希望该算法也对遍历的节点数量给予一定的权重。

因此，从A到B计算的最短路径在某些值下可能不会必须是最短路线，但节点数量最少的路线。

对此有何看法？

欢呼声，

RD

编辑：

我的道歉。我应该更好地解释。因此，可以说，从
（A，B）开始的最短路线是A - > C - > D - > E - > F - > B，共计10个单位 -
但我想要算法提出的路线A - > M - > N - > B共包含12个单位。

所以，我想要的是能够赋予一定的权重到节点的数量，而不仅仅是连接节点的距离。

解决方案

让我证明，添加一个常量值到所有边缘可以改变哪条路线是最短（边缘的最小总重量）。

这是原始图形（一个三角形）：

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

从A到B的最短路径是通过C.现在将常量2添加到全部边缘。最短路径变成了从A直接到B的单个步骤（由于我们已经介绍了使用额外边的惩罚）。注意，边的数量使用的是（不包括你开始的节点）与访问的节点数相同。

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

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.

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.

Any thoughts on this?

Cheers,
RD

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

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屋！