Wyszukiwanie najbliższej trasy po sąsiadach

Witam. Posiadam obiekt w którym znajduje się około 2400 elementów. Każdy element jest kolejnym obiektem zawierające dwie dane nazwe oraz tablice. Tablica jest to znowu lista sąsiadów. Szukam sposobu jak wykorzystując tablice sąsiadów znaleźć najkrótszą trase miedzy dwoma elementami (na zasadzie mapy). Przykłąd elementów :

{
    "1": {
        "name": "a",
        "teleports": ["138", "34", "2720", "13", "191", "17", "2712", "26", "7", "610", "2713", "8", "3130", "2665", "297", "967", "5", "2517", "2711", "18", "333", "15", "2663", "11"]
    },
    "2": {
        "name": "b",
        "teleports": ["2029", "66", "73", "69", "2002", "68", "3986", "2217", "2213", "70", "2199", "12", "1111", "76", "71", "78", "82", "80", "354", "2197", "2206", "1108"]
    },
    "3": {
        "name": "v",
        "teleports": ["11", "4", "19", "12", "634", "5735", "5733", "633", "631"]
    },
    "4": {
        "name": "d",
        "teleports": ["110", "3", "2524"]
    },
    "5": {
        "name": "e",
        "teleports": ["6", "1"]
    },
    "6": {
        "name": "g",
        "teleports": ["5", "380", "375", "369", "379", "374", "370", "378", "373", "371", "377", "372", "376"]
    }
}

To jest przykłąd kilu elementów, obecnie w spisie znajduje się około 2400. Jako klucz jest użyte ID danego elementu, w tablicy teleports sa ID sąsiednich elementów. Pomysłem jest funckcja pobierajaca dwa argumenty, Poczatek i Koniec. Pobieram teleports z Koniec, sprawdzam czy jest Poczatek, jak nie to pobieram każdy obiekt z teleports i ponawiam sprawdzenie, az do skutku (na zasadzie rekurencji), ale tego jest zbyt sporo. Nie mam pomysłu już. Ps. taki obiekt mogę łatwo zamienić na tablice z elementami ID|Name|teleports może ułatwiłoby przeszukiwanie dzięki wbudowanymi funkcjami w Array z JS.

To wyglada na BFS

albo https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

MrMuniez napisał(a):

Pomysłem jest funckcja pobierajaca dwa argumenty, Poczatek i Koniec. Pobieram teleports z Koniec, sprawdzam czy jest Poczatek, jak nie to pobieram każdy obiekt z teleports i ponawiam sprawdzenie, az do skutku (na zasadzie rekurencji), ale tego jest zbyt sporo. Nie mam pomysłu już. Ps. taki obiekt mogę łatwo zamienić na tablice z elementami ID|Name|teleports może ułatwiłoby przeszukiwanie dzięki wbudowanymi funkcjami w Array z JS.

1. Albo masz elementy wewnątrz uporządkowane i wtedy oczywiście robisz tablice a nie obiekt, chyba że właściwość 'name' jest unikalna, to wtedy ona jest kluczem name:[ teleports ].
2. Generalnie jesteś na dobrej drodze moim zdaniem, mniej więcej w ten sposób to trzeba zrobić, tylko że taki algorytm ma koszmarne Big O notation, więc dla tablicy z 2k elementów oczywiście się wysypie. Natomiast dość prosto można cały proces zoptymalizować. Tworzysz sobie tablicę na najwyższym poziomie funkcji. Za każdym razem, gdy sprawdzasz jakiegoś noda to go pushujesz do tej tablicy, jako 'sprawdzony' i potem jak na niego natrafiasz w kolejnym obiekcie to już go pomijasz dzięki czemu nody nie pączkują w nieskończoność. I tak interesuje Cię najtkrótsza ścieżka, więc to, że można dojść do celu 'naokoło' nie ma znaczenia. Zrobiłem coś podobnego dla obliczania ruchów konia w szachach, tylko tam nie trzeba było niczego optymalizować, bo możliwych ruchów nie jest aż tak dużo. Patrząc na Twoje umiejętności, myślę że spokojnie to ogarniesz. Pozdrawiam

Panowie, dziekuje za pomoc, adaptacja BFS chyba działa wyśmienicie w tym przypadku, co do samej struktury jak kolega wyżej pyta, strukturę chce zostawić, ponieważ parametr |name| jest zawracany do UI użytkownika. A ponieważ cała mapa jest spisana z zewnętrznego źródła postanowiłem całościową mapę (wraz właśnie z nazwą) na raz zapisać w plik i spakować razem do aplikacji. Co do Djikstry jak kolega @MarekR22 podał, sprawdzałem, ale większość przykładów jest na grafie ważonym, w moim przypadku w teorii każde połączenie to koszt 1, lecz nie wiedziałem jak go zaimplementować.
@lion137 trafna uwaga, po zainteresowaniu się tym algorytmem od razu zauważyłem ze jest on w "nurcie" mojego pomysłu, wystarczyła tylko adaptacja. I tak pomogłem sobie przykładem z Internetu (bo od czego go mamy ). Postanowiłem tylko przeanalizować kod, i odpowiednio przygotować dane wejściowe.

const fs = require("fs");

var maps = JSON.parse(fs.readFileSync("ids3.txt"));

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.shift();
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

function bfs(graph, start, end) {
  if (start === end) {
    return [start];
  }

  const queue = new Queue();
  const visited = {};
  const path = {};

  queue.enqueue(start);
  visited[start] = true;

  while (!queue.isEmpty()) {
    const currentVertex = queue.dequeue();

    if (graph[currentVertex]) {

      for (const neighbor of graph[currentVertex]) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          path[neighbor] = currentVertex;
          if (neighbor === end) {
            // Rekonstrukcja najkrótszej ścieżki
            const shortestPath = [end];
            let prevVertex = path[end];
            while (prevVertex !== start) {
              shortestPath.unshift(prevVertex);
              prevVertex = path[prevVertex];
            }
            shortestPath.unshift(start);
            return shortestPath;
          }
          queue.enqueue(neighbor);
        }
      }
    }
  }

  return null; // Jeśli nie znaleziono ścieżki
}

// Przykład użycia
const graph = {};
for (var ele in maps) {
  graph[ele] = maps[ele].teleports;
}
const startVertex = "1";
const endVertex = '33';
const shortestPath = bfs(graph, startVertex, endVertex);
if (shortestPath) {
  console.log("Najkrótsza ścieżka:", shortestPath);
} else {
  console.log("Nie ma ścieżki między podanymi wierzchołkami.");
}

Ps. zmienna $maps to nic innego jak pełny obiekt około 2400 elementów pobierany z pliku.