Najkrótsza Droga

[DiJo]

elo :) mam do napisania algorytm, który policzy najkrótszą drogę między dwoma punktami. Znalazłem w necie coś takiego: Algorytm_Dijkstry ale nie zabardzo to rozumiem :) czy jak zrobie w ten sposób, że policze drogę od pierwszego wierzchołka do każdego z którym on sąsiaduje, pozniej z każdego z nich do kolejnych z którymi sąsiaduje itd... to bedzie duzo bardziej złożone od Dijkstry? Może ktoś to zna i mi wytłumaczy tak jakoś prosto =]

[Allen]

Alg. Dijkstry zdaje się być najbardziej optymalnym wyborem algorytmu dla przypadku znajdowania najkrótszej drogi pomiędzy dwoma punktami.

 

Dla alg. znajdowania drogi pomiędzy każdą parą wierzchołków w sieci wykorzystałbyś już alg. Floyda.

 

czy jak zrobie w ten sposób, że policze drogę od pierwszego wierzchołka do każdego z którym on sąsiaduje, pozniej z każdego z nich do kolejnych z którymi sąsiaduje itd... to bedzie duzo bardziej złożone od Dijkstry?

To zależy jak rozumieć tok Twojego rozumowania.

 

Przypadek I

Liczymy drogę od pierwszego wierzch. do każdego, z którym sąsiaduje, później z każdego z nich do kolejnych wierzch., z którymi każdy z nich sąsiaduje i później wybieramy najkrótszą drogę.

Będzie to zdecydowanie zbyt złożone pod względem czasowym i mało wydajne, bo na darmo męczymy się z wyznaczaniem wszystkich możliwych dróg, z których później musimy dodatkowo wybrać MIN()!

 

Przypadek II

Liczymy drogę od pierwszego wierzch. (nazwijmy go A) do każdego, z którym sąsiaduje, wybieramy drogę o najmniejszej wadze (może to być, np. jej długość, odl. pomiędzy dwoma miastami), liczymy drogę od drugiego wierzchołka do sąsiadujących z nim i wybieramy najkrótszą drogę z pośród wszystkich dostępnych dróg (zarówno od 1 jak i 2 wierzchołka) i wybieramy drogę o najmniejszej wadze, analogicznie postępujemy w kolejnych krokach, dopóki nie dotrzemy do celu wyprawy, wierzchołka docelowego (nazwijmy go B).

Na tym generalnie polega alg. Dijkstry, i nie wymaga to bezproduktywnego wyliczania wszystkich możliwych dróg z pkt. A do B.

 

Poniżej załączam, myślę w miarę zrozumiały obrazowo, alg. dijkstry - na przykładzie prostego grafu.

 

Część teoretyczna:

 

Część praktyczna:

Ostatni - 4ty - krok powinien mieć kolejność {1,2,4,3,5}.

Edytowane 9 Czerwca 2006 przez Allen3