-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

Improve this question
$\endgroup$
3
  • $\begingroup$ How can the number of shortest paths be 0 if A and O are connected? $\endgroup$
    – le_garry
    Mar 6, 2013 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, 2013 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, 2013 at 11:16

3 Answers 3

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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