Jaki algorytm??

Witam
Z przedmiotu "Algorytmy i struktury danych" dostałem następujący projekt do wykonania:

Napisać program znajdujący przejście przez zadaną planszę. Plansza składa się z dróg i komnat, które reprezetują skrzyżowania. Do każdej komnaty można wejść tylko jeden raz.

Co do algorytmu, to myślałem że użyję tutaj algorytmu Prima lub Kruskala, które operują na grafach, ale raczej to odpada. Jaki algorytm mogę użyć do wyznaczenia tej drogi??

cykl hamiltona ;) lub droga hamiltona

ogolnie problem komiwojazera - jest duzo algorytmow

Ani cykl hamiltona ani problem komiwojażera. Nie jest powiedziane, że:

• trzeba wejść do każdej komnaty (cykl hamiltona, problem komiwojażera)
• ma to być najkrótsza droga (problem komiwojażera)
• musimy wrócić do punktu startowego (cykl hamiltona)

Problem rozumiem w ten sposób, że mamy znaleźć dowolną drogę w jak najkrótszym czasie.
Wydaje mi się, że DFS będzie dość szybki.

wisnia01: popraw temat, przynajmniej dopisz, że o graf chodzi.

@adf88
w sumie racja:D
a w takim razie propnuje algorytm Dijkstry

Johny_Morfina napisał(a)

@adf88
w sumie racja:D
a w takim razie propnuje algorytm Dijkstry
Heh, ale algorytm Dijkstry też szuka najkrótszej drogi