A Shortest Path Algorithm With Minimum Number Of Nodes Traversed

1
votes

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.

4
graphshortest-pathdijkstra
You can modify the weights, increasing each edge by a constant, which penalizes using more edges (equiv. more nodes) in a path. Basically you need to articulate more clearly what objective function is being minimized. – hardmath
You've given conditions that are too vague to really be helpful. This is an ill-formed question. One obvious comment: if the nature of taking the number of nodes traversed into account is additive, then consider adding a uniform amount to your weights to make each node traversal take a uniform amount longer. – Kaganar
It sounds like you're saying: The route you return MUST be the shortest number of nodes traversed, but in addition, of all solutions that are the shortest number of nodes traversed, you want the least edge weight? – Jeremy
@hardmath : If I uniformly increase all edges, then there is no change in the shortest path computed. – Rohitesh
@Kaganar : I hope after the edit, my question is clearer. – Rohitesh

4 Answers

6
votes

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.

2
votes

The way you can do that is adapt the weights of the edges to always be 1, so that you traverse 5 nodes, and you've gone a distance of "5". The algorithm would be the same at that point, optimizing for number of nodes traversed rather than distance traveled.

If you want some sort of hybrid, you need to determine how much importance to give to traversing a node and the distance. The weight used in calculations should look something like:

weight = node_importance * 1 + (1 - node_importance) * distance

Where node_importance would be a percentage which gauges how much distance is a factor and how much minimum node traversal is important. Though you may have to normalize the distances to be an average of 1.

1
votes

I'm going to go out on a limb here, but have you tried the A* algorithm? I may have understood your question wrong, but it seems like A* would be a good starting point for what you want to do.

Check out: http://en.wikipedia.org/wiki/A*_search_algorithm

Some pseudo code there to help you out too :)

1
votes

If i understood the question correctly then its best analogy would be that used to find the best network path.

In network communication a path may not only be selected because it is shortest but has many hop counts(node), thus may lead to distortion, interference and noise due to node connection.

So the best path calculation contains the minimizing the function of variables as in your case Distance and Hop Count(nodes).

You have to derive a functional equation that could relate the distance and node counts with quality.

so something as suppose
1 hop count change = 5 unit distance (which means the impact is same for 5unit distace or 1 node change)

so to minimize the loss you can use it in the linear equation.
minimize(distance + hopcount);
where hopcount can be expressed as distance.