Algorytm szukający trasy w grafie.

Question

Witam, mam taki kod

function getNeighbours(id, ignore) {
    return Relation.find({
        $and: [
            { _id: { $regex: `.*${id}.*` } },
            { _id: { $not: { $regex: `.*${ignore}.*` } } }
        ]
    }).exec();
}

console.log(await getNeigbours(1, 0));
// wynik: [ { _id: '1-2', distance: 1.8 }, { _id: '1-8', distance: 3.7 } ]

To jest zapytanie do bazy mongodb które wyszukuje relację pomiędzy dwoma punktami (_id wygląda np. tak "1-2"; "1-8"). Zwraca wszystkie połączenia punktu start, może ignorować połączenia z innym punktem aby nie wracać do poprzedniego punktu jeśli wyszukuje trasę. Wartość "distance" jest tutaj nieistotna.

Przykładowo mam punkty łączące się w następujący sposób 9-8-1-2-3-4-5-6-7 (punkty nie muszą mieć następujących po sobie id, może być to również 512-29-820...) i chcę znaleźć trasę z punktu 1 do 6. Manualne rozwiązanie wyglądałoby tak:

console.log(await getNeigbours(1, 0));
// wynik: [ { _id: '1-2', distance: 1.8 }, { _id: '1-8', distance: 3.7 } ]
console.log(await getNeigbours(2, 1));
// [ { _id: '2-3', distance: 4.9 } ]
console.log(await getNeigbours(3, 2));
// [ { _id: '3-4', distance: 5.2 } ]
console.log(await getNeigbours(4, 3));
// [ { _id: '4-5', distance: 2.2 } ]
console.log(await getNeigbours(5, 4));
// [ { _id: '5-6', distance: 6.2 } ]

Ja próbowałem i nie działa mi dobrze już od wyszukiwania sąsiadów sąsiadów punktu początkowego, jak wstawiam w pętlę to nie zwraca nawet błędnego wyniku.

let start = 1;
let ignore = 0;
neighbours.push(await getNeighbours(start, ignore));
    ignore = start;
    neighbours[0].forEach(async neighbour => {
        const neighboursArray = (neighbour.toJSON()._id).split("-");
        const indexOfIgnored = neighboursArray[0] == ignore ? 0 : 1;
        start = indexOfIgnored ? neighboursArray[0] : neighboursArray[1];
        ignore = indexOfIgnored ? neighboursArray[1] : neighboursArray[0];
        console.log("> ", "Sąsiad", neighbour, "Sąsiedzi", neighboursArray, "Ignorowane", parseInt(ignore), "Miejsce Ignorowanego", indexOfIgnored);
        neighbours.push(await getNeighbours(start, ignore));
        console.log(await getNeighbours(start, ignore));
    });
// Wynik
// >  Sąsiad { _id: '1-2', distance: 1.8 } Sąsiedzi [ '1', '2' ] Ignorowane 1 Miejsce Ignorowanego 0
// >  Sąsiad { _id: '1-8', distance: 3.7 } Sąsiedzi [ '1', '8' ] Ignorowane 1 Miejsce Ignorowanego 0
// [ { _id: '8-9', distance: 2.3 } ]
// [ { _id: '8-9', distance: 2.3 } ]

Powinno być 

// >  Sąsiad { _id: '1-2', distance: 1.8 } Sąsiedzi [ '1', '2' ] Ignorowane 1 Miejsce Ignorowanego 0
// >  Sąsiad { _id: '1-8', distance: 3.7 } Sąsiedzi [ '1', '8' ] Ignorowane 1 Miejsce Ignorowanego 0
// [ { _id: '8-9', distance: 2.3 } ]
// [ { _id: '2-3', distance: 4.9 } ]

Może ktoś zna jakiś sposób na to jak to "skleić" aby wykonywało się automatycznie?

Comments

Czemu w ten sposób reprezentujesz graf? Nie lepiej listą list i w odpowiednich listach trzymasz sąsiadów grafu. Algorytm Dijkstry wyznaczy najkrótszą trasę i ścieżkę

---

No są sposoby lepsze i gorsze, a od któregoś trzeba zacząć, ten jest dla mnie najprostszy, bo zajmuje najmniej miejsca i kod potrzebny do odczytania tych wartości jest krótszy w przeciwieństwie do listy z listą sąsiadów punktu. A co do algorytmu. Żaden przykład znaleziony przeze mnie w internecie, czy wytłumaczenie dotyczące algorytmu Dijkstry czy A* niestety nie objaśnia mi tego w jaki sposób powinienem dalej to pociągnąć.

---

Może ciebie źle zrozumiałem, masz strukturę grafu, i chcesz znaleźć ścieżkę z wierzchołka A do wierzchołka B?

---

Tak, moja koncepcja na to wygląda tak: sprawdzane są wszystkie punkty sąsiadujące z punktem początkowym i ich następni sąsiedzi, dopóki nie znajdzie się wśród nich punkt końcowy. Jakoś tak to będzie, to jest taki mój pierwszy kontakt z jakimś bardziej poważnym algorytmem, więc stąd cały problem.

---

https://www.flynerd.pl/2018/10/reprezentacja-maszynowa-grafu-czym-jest-graf.html

Tutaj masz różne reprezentacje grafu, najwygodniejsza jest lista sąsiadów. Jeśli nie ma dla ciebie znaczenia długość tej ścieżki, to możesz użyć albo BFS albo DFS. Idziesz np. BFS po grafie i zaznaczasz w każdym wierzchołku poprzednika (z którego wierzchołka przyszedłeś do tego grafu) gdy dotrzesz do miejsca docelowego to wracasz się po poprzednikach i masz całą ścieżkę

---

Dzięki