Hi,
working on the RCSP algorithm, I have come to realise that when using the single shortest path interface for RCSP, it is not alway what is returned.

Now before submitting a fix, I would like to understand whether this is a bug or my misunderstanding.

Let me try to explain:

• The RCSP does not explicitly deal with the distance that define which path is the shortest, but rather asks that when extending a label l1 to the next l2, then l1<=l2
• The RCSP uses the <operator to process labels from the priority queue so that the "smallest" one is picked up at each iteration.
• If l1<=l2 implies that the distance increases from l1 to l2, then
  • at each iteration RCSP processes the label with the smallest distance so far
  • when a label at the target is processed, any other label has at least the same distance, thus we have found one of the possible shortest path.

All sounds good. However, when the algorithm terminates there is an additional step to reconstruct the solution. It iterates over the labels stored in a list at target vertex, and use the first one as the single best solution. But those labels are not sorted using the < but rather they are in order of extension. This mean that the post-processing can return another path than the one that was found by the algorithm itself!

I have create a four node example that I think shows what happens, and it is attached.
rcsp-bug-submission.zip

To me it is, as the RCSP must return the shortest path (hence the SP in the name) if labels are first sorted by the distance first. Clearly, if one asks for all non-dominated solutions, then this is not an issue anymore.

Is this a bug?