lua - get "path" of connected ids

Question

I'm just confusing myself over and over ... I have the following table containing the information which id is connected to what other ids. And I need to find the "cheapest" connection from ID1 to ID2

local ids = {
   [15] = {
      [18] = {
      },
      [23] = {
      },
      [24] = {
      },
   },
   [18] = {
      [15] = {
      },
      [21] = {
      },
      [50] = {
      },
      [248] = {
      },
      [330] = {
      },
      [378] = {
      },
      [914] = {

      },
      [1185] = {
      },
   },
   [21] = {
      [18] = {
      },
      [20] = {
      },
   },
   [248] = {
      [18] = {
      },
   },
}

The expected result is:

local table_path = {
   15,
   18,
   21,
}

question from:https://stackoverflow.com/questions/66062206/get-path-of-connected-ids

Answer 1

I guess the cheapest connection should be the shortest, so what you want to do is a Breadth-first search. you need to save the path to each node additionally since this is what you want to get. Once you have found ID2 you can stop and take the path. Since this is Breadth-first, the first time you find ID2 is also guaranteed to be the shortest path.

https://en.wikipedia.org/wiki/Breadth-first_search

I just searched a bit more and found that:

BFS algorithm using Lua that finds the shortest path between 2 nodes

In the answer to this there is an implemented Breadth-first search in Lua. You could start from this and make changes for your use case if needed.