|
|||
Najkrótsze ścieżkiMonika bardzo lubi jeździć
konno. Tym razem jedzie w wyścigu. Do celu
można dotrzeć różnymi drogami, Monika
zaznaczyła je na mapce wraz z czasami
potrzebnymi na ich przejechanie. Którą trasę
powinna wybrać, aby przyjechać na miejsce jak
najszybciej?
Mamy dany graf skierowany ważony i wyróżnione dwa wierzchołki. Aby wyznaczyć najkrótszą ścieżkę pomiędzy nimi możemy użyć algorytmu Dijkstry. Algorytm Dijkstry znajduje w grafie wszystkie najkrótsze ścieżki pomiędzy wybranym wierzchołkiem a wszystkimi pozostałymi, przy okazji wyliczając również koszt przejścia każdej z tych ścieżek. Działanie algorytmu pokazane zostało poniżej: Możemy też użyć bardziej ogólnego
algorytmu Bellmana-Forda - działa wolniej niż algorytm
Dijkstry, ale działa także w przypadku grafów, gdzie
wagi krawędzi są ujemne.
|
|||
Created by Monika Ciosek |