0

I've stumbled upon a question which is similar to the shortest distance in leetcode, however this is from an array of tuple instead of nodes

I've also read the similar question here Shortest path between connected pairs of tuples

However, I still couldn't really figure out a way that will be able to solve this efficiently.

Find the least number of hops needed to get from ID=1 to ID=15 using the array
tuple provided below. 

For example, to get from ID=1 to ID=4 will require 2 hops
– [1,3] follow by [3,4].

    x = [[1,2], [1,3], [3,4], [4,5], [5,6], [5,7], [1,7], [2,8], [8,9], [9,11], [9,10], [7,10],
    [10,12], [10,14], [12,13], [14,15]]

My current solution (not yet completed) is to convert it into a graph which looks like the following

  '1' => [ '3', '7' ],
  '2' => [ '8' ],
  '3' => [ '4' ],
  '4' => [ '5' ],
  '5' => [ '6', '7' ],
  '6' => [],
  '7' => [ '10' ],
  '8' => [ '9' ],
  '9' => [ '11', '10' ],
  '10' => [ '12', '14' ],
  '11' => [],
  '12' => [ '13' ],
  '13' => [],
  '14' => [ '15' ],
  '15' => []

Then try to recursively do DFS and get the shortest path.

The issue with this solution is that

  1. I need to convert the data to a graph, which is at least O(n)
  2. Only then I can do DFS to get to the solution.

My question is, are there any efficient way other than converting the tuple to graph?

Im thinking of sorting the array of tuple before looping it. Or could just narrow down the array of tuple to those that are within the start and end, then try to loop from there.

PKiong
  • 521
  • 4
  • 13
  • In fact, your list of tuples (=edges) is already a graph, you just need an efficient data structure to quickly retrieve adjacent nodes as you walk it. Of course you can search the edge list linearly or sort it and apply bsearch, but that would be more expensive than converting it once in the beginning. – georg Mar 15 '21 at 16:24
  • Yeah, it is sort of like graph, but its hard to work with since the array given is not guaranteed to be sorted by x then y (x being first element, y being second element of tuple). – PKiong Mar 15 '21 at 16:34

0 Answers0