Dijkstra uzyskanie drogi po wierzchołkach

Witam, czy mógłby mi ktoś pomóc z uzyskaniem z tego kodu drogi "po wierzcholkach"?
Trasy z poczatkowego zrodla do skrajnych wierzcholkow obliczają się prawidłowo, aczkolwiek nie mam pomysłu jak tutaj uzyskać drogę, która trzeba przejść żeby taka odleglosc uzyskać.
https://pastebin.pl/view/42bfce20 kod całego programu.
funkcja dijkstra zaczyna się od 63 linii, do 121.
Pozdrawiam.

Masz tablice odleglosci. Musisz miec jeszcze tablice poprzednikow.

@stivens: Czy mógłbyś bardziej rozjaśnić temat?
Próbowałem stworzyć vector<vector<string>> dla którego zapisywać w poszczególnych wierszach trasy, ale nie potrafię zrozumieć jak z tego kodu wyciągać miasta dla danej trasy :/

Nie czytalem Twojego kodu wiec nie odniose sie bezposrednio do niego.

"krok" w Dijkstrze wyglada tak:

nowa_odleglosc = | start -> przetwarzany_wierzcholek -> v |
jesli nowa_odleglosc jest mniejsza_niz najkrotsza_odleglosc[v]:
    najkrotsza_odleglosc[v] = nowa_odleglosc

zeby wyznaczyc trase to trzeba dolozyc zapamietywanie poprzednika:

nowa_odleglosc = | start -> przetwarzany_wierzcholek -> v |
jesli nowa_odleglosc jest mniejsza_niz najkrotsza_odleglosc[v]:
    najkrotsza_odleglosc[v] = nowa_odleglosc
    poprzednik[v] = przetwarzany_wierzcholek

Zeby wyznaczyc trase to powtarasz:

1. Wyciagnij poprzednik wierzcholka i przejdz do niego
2. Jesli jestes na starcie to zakoncz dzialanie, wpp. powtorz od 1