Jednokierunkowy algorytm Dijkstry

0

Muszę zaimplementować w C++ jakiś algorytm obliczający najkrótszą ścieżkę pomiędzy miastami. Dijkstra do tego chyba dobrze się nadaje, jednak problem w tym, że w zadaniu wszystkie drogi pomiędzy miastami są jednokierunkowe. Googlowałem hasła typu 'dijkstra one-way', 'dijkstra indirectional', 'shortest path indirectional' - na próżno. Wręcz proponowało mi 'czy chodzi ci o bidirectional?'.

Problem polega też na tym, że nie jestem zaznajomiony z grafami, klasami, setami, pairami, priority queue'ami i innymi nigdy dotąd spotykanymi mi rzeczami w implementacjach Dijkstry - sam od zera nie umiałbym napisać tego algorytmu, więc pozostaje mi próba analizy gotowych rozwiązań. Nie potrafię gotowego algorytmu zmienić tak, aby działał dla dróg jednokierunkowych.

Przykładowy graf graf mógłby wyglądać np. tak:
imgur

Jakieś sugestie?

2

jednak problem w tym, że w zadaniu wszystkie drogi pomiędzy miastami są jednokierunkowe

A co to za problem? To oznacza, że masz graf skierowany (directed) zamiast nieskierowanego, ale algorytm Dijkstry działa tak samo, o ile tylko nie masz ujemnych cykli.

0

Czy w ogóle ten graf jest ważony? Bo jeśli nie jest, no to wystarczy BFS.

0

Tak, graf jest ważony (tylko dodatnie wagi dozwolone).

0

W takim razie nie masz żadnego problemu — algorytm Dijkstry nie będzie mieć kłopotów z Twoim grafem, on nie wymaga dwukierunkowości ścieżek.

1 użytkowników online, w tym zalogowanych: 0, gości: 1