Czesc
Sory ze tu, ale pisze w Delphi a poza tym ten dzial jest chyba najpopularniejszy:)
Szukam jakiegos kursu gdzie jest przystepnie wyjasniony algorytm wyszukiwania najkrotszej drogi z wezla A do B
czy ktos wie cos na ten temat??
pzdrw
0
0
http://www.algorytm.cad.pl/ ->algorytmy grafowe
0
Moze dokladniej ..... bo kurde ja to rozumiem co najmniej na 10 sposobow. Np. w labiryncie itp.
Bez labiryntu chyba by było łatwo, co?
0
moze i latwo ale chyba nie do konca o tym samym mowimy, bo rzeczywiscie nie dokladnie to zprecyzowalem.
(A)---[5]--->(B)---[4]--->(C)
| |
[2] [1]
| |
(D)---[1]--->(E)---[1]--->(F)
mamy taki graf (w okraglych nawiasach sa Wezły a w kwadratowych koszt przejscia)
Teraz mi chodzi o znalezienie najkrotszej (najtanszej) drogi np z A do C.
Droga optycznie najkrotsza (A-B-C) ma koszt 5+4 = 9.
A poprawne rozwiazanie powinno byc:
A-D-E-F-C koszt 2+1+1+1 = 5.
i o cos takiego mi chodzilo
tylko zeby to komputer liczyl a nie ja:)
pzdrv
0
Bellman-Ford (bez cykli ujemnych), Dijkstra (bez ujemnych krawedzi) lub jezeli chcesz kazdy z kazdym miec od razu to FloydWarshall.
Dzieki temu otrzymasz wartosci najkrotszych drog. Majac to mozesz juz spokojnie wyznaczyc konkretne wierzcholki, po ktorych trzeba przejsc. Majac odleglosc od wierzcholka startowego do wszystkich pozostalych wybierasz taki przedostatni wierzcholek, ktorego suma odleglosci poczatek-wierzcholek i wierzcholek-koniec jest rowna tej wartosci. W ten sposob masz juz przedostatni wierzcholek. Nastepnie bierzesz przed przedostatni i analogicznie bierzesz poczatek-wierzcholek + wierzcholek-przedostatni = poczatek-przedostatni. Itd.