[Solved]: Dijkstra algorithm: equal number of shortest paths

Problem Detail: 

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:

Asked By : joker

Answered By : wookie919

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10333