How to find the lexicographically smallest path among the shortest paths in a graph?

help
, ,
1

For example we have the following graph:
number of nodes = 3 (0,1,2)
number of edges = 3
from to cost
0 1 1
0 2 2
1 2 1

Now if we want to go from 0 to 2, there is two shortest path :

  1. 0 -> 2 . cost = 2
  2. 0 ->1->2 cost = 2

But 0 -> 1 -> 2 is lexicographically smaller. So this is my answer. For larger inputs how can I always get the correct output?

2

I take it that you know how to find the shortest path between two nodes of a graph, using breadth-first search or a similar technique. In that method you need to store the lowest cost to each node so far. Instead store both the lowest cost and the lexicographic path, and when two paths have the same cost choose the one with the lower lexicographic path.

2 Likes
3

You mean I should store the whole path from root to the current node in a string or likewise data structure for every node?

5

Yes, exactly so. Then you can compare them immediately.

6

I don’t think so that your idea will pass time limit. Need a better and efficient approach.

7

Here is a problem based on above topic. The Flight Plan | Practice Problems

The problem did pass within the time limits by the method prescribed above.
Here is my code for it.
Submission (59515387) for The Flight Plan | HackerEarth.