Ścieżka od A do B przez zbiór zadanych wierzchołków

Witam,
muszę napisać aplikację wykonującą 2 następujące czynności:
-znajdywać najkrótszą drogę pomiędzy 2 zadanymi wierzchołkami - proste, można użyć Dijkstry, bo wagi krawędzi mają być dodatnie
-znajdywać najkrótszą drogę pomiędzy zadanymi wierzchołkami odwiedzając po drodze zbiór wyszczególnionych wierzchołków (w dowolnej kolejności, byle odwiedzić).

I właśnie mam pytanie, w jaki sposób można to zrobić? Bo jedyny jaki mi na razie przychodzi do głowy, to sprawdzenie wszystkich możliwych kolejności odwiedzenia pośrednich wierzchołków i wybranie najkrótszej wersji. Ale czy nie da się tego zrobić jakoś sprytniej??

Poszukaj takiego hasła:
http://www.google.pl/search?q=problem+komiwojażera

Na forum też to się przewijało..

Źle przeczytałem kurcze polecenie. Druga część programu ma po prostu odnajdywać drogę między wybranymi wierzcholkami przez zbiór zadanych miejscowości odwiedzanych w dowolnej kolejności, koszt podróży nie gra roli.

Zadanie sporo ułatwione, ale wciąż nie mam wyraźnego pomysłu jak to zrealizować. Czy ktoś może pomóc jakąś sugestią ??

Wpadłem na pomysł, żeby ze zbioru miejscowości, które są do odwiedzenia, wziąć tę, która leży najbliżej miejsca startu i wrzucać ją na listę kolejności trasy. Potem kolejną, która leży najbliżej ostatnio wyjętej i tak aż do miejscowości docelowej.

To chyba jest dobry pomysł ??

Taaa... Jakiś czas temu wpadł na to niejaki Dijkstra. Od tamtej pory jest to jeden z najczęściej wykorzystywanych algorytmów szukania drogi :)

Skoro koszt nie gra roli to po co wybierać najbliższą drogę ? Do metody którą wymyśliłeś trzeba by odpalać algorytm Dijkstry dla każdej miejscowości do odwiedzenia, niepotrzebnie.
Ja bym tu po prostu odwiedzał każde miasto po kolei odnajdując do niego drogę DFS'em. W tej metodzie dla każdej miejscowości do odwiedzenia trzeba odpalić DFS'a, który będzie szybszy od algorytmu Dijkstry bo nie trzeba odwiedzać wszystkich wierzchołków ani odwoływać się do kosztów.

gotowe algorytmy takie i inne są w biblitece boost
http://www.boost.org/doc/libs/1_34_0/libs/graph/doc/dijkstra_shortest_paths.html