najkrotsze sciezki

Najkrótsze ścieżki

Monika 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:
dijkstra

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.


STRONA GŁÓWNA WPROWADZENIE DO GRAFÓW RODZAJE GRAFÓW PRZESZUKIWANIA W GRAFACH GRAFY HAMILTONOWSKIE GRAFY EULEROWSKIE NAJKRÓTSZE ŚCIEŻKI SORTOWANIE TOPOLOGICZNE
	Najkrótsze ścieżki Monika 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