-1
$\begingroup$

If I had a Dijkstra graph with the number shortest paths from Node A to O being 1, would it be correct to say: the equal number of shortest paths from A to O is 1 and not 0, because that node is included as an 'equal shortest path'? I am really confused.

Here is an image to illustrate my question:

automaton

$\endgroup$
  • $\begingroup$ How can the number of shortest paths be 0 if A and O are connected? $\endgroup$ – le_garry Mar 6 '13 at 21:00
  • $\begingroup$ the equal number of shortest paths, the shortest path is 4 from A to O at the moment $\endgroup$ – joker Mar 6 '13 at 21:05
  • $\begingroup$ Assuming you mean "the number of equal-length shortest paths", that number still cannot be zero. (I have no idea what else "the equal number of shortest paths" might mean.) $\endgroup$ – JeffE Dec 22 '13 at 11:16
2
$\begingroup$

Depends on how you define "equal number of shortest paths".

If we change the graph so that Q -> O is 3, then we have two shortest paths from A to O, one via P and one via Q, both of distance 4.

Then there are 2 shortest paths with equal distances. This is what you mean by "equal number of shortest paths", correct?

Then, the question is, when there is just 1 shortest path as in the original graph, should we say "there is 1 shortest path with equal distance", or is it more correct to say "there is 0 shortest path with equal distance"?

Both are correct depending on how the question is phrased.

  1. How many shortest paths are there in total that have equal distances?
  2. How many additional paths are there that have distances equal to the given shortest path?

This is simply a wording problem and not so much a Technical Computer Science Shortest Path Algorithm problem.

$\endgroup$
1
$\begingroup$

There will be atleast one shortest path from source to destination. There can be multiple shortest paths from source to destination but Dijkstra will choose only one based on the nearest neighbors.

This will give you a good idea on how Dijkstra works.

$\endgroup$
1
$\begingroup$

As wookie said,You are right in your essence rather wrong in how you are presenting it.,

It would be more correct if you say "*There is 1 shortest path from source to destination or There are 2 shortest path from source to destination *,rather than saying " the equal number of shortest paths is 1"

And therefore if you have more than one shortest path it implicitly means that the shortest paths are having equal distances.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.