Algorytm Dijkstry

Ze Wikipedia
Przejdź do nawigacji Przejdź do wyszukiwania
Dźołańy algorytmu uod Dijsktry na bajszpilu. Anfang je we knoće a, na modro naszkryflane sům aktuelńy nojkrůtsze wysznupane dugośći dojśćo do knota. Wyńikym je, aże ze knota 1 do 5 nojkrůtszo droga mo dugość 20.

Algorytm uod Dijsktry - algorytm zbajstlowany bez ńiderlandzkego informatikera Edsgera Dijkstre do znojdowańo nojkrůtszyj drogi we grafje ze wybranygo knota do ryszty knotůw. Algorytm ńy dźało kej ftoroś kanta mo ujymny wert.

Dźołańe[edytuj | Edytuj zdrzōdło]

Nojsamprzůd dany momy graf a wybrany jedyn jigo knot, ze kerygo bydymy sztartować.

  1. Naszkryflej lista wszyjskich knotůw i naszkryflej przi kożdym knoće, aże dugość drogi do ńygo je růwno ńyskończůność, tak co potym do śe to bydźe sprowjać.
  2. Půdź do sztartowygo knota, zaś na liśće sprowjej wpisano przi ńim ńyskończůność i zastůmp ja nůmerům 0.
  3. Zobocz kaj prowadzům bezpostrzedńo kanty ze knota przi kerym żeś je. Skreślij kanty kere prowadzům do skreślůnych knotůw[1]. Lo kożdyj kanty zrůb to samo:
    • Dodej dugość dojśćo do knota przi kerym żeś je ze wertym (dugośćům) kanty[2]. Zobocz czy na liśće knot do kerego dano kanta prowadźi je uoznaczůny majsům nůmerům[3]. Eli ja to ńy růb nic, eli ńy to sprowjej aktuelno dugość drogi na ta, ftoro će wyszła ze uobliczyńo[4].
  4. Zobocz na liśće, kery knot mo nojkrůtszo droga dojśćo. Půdź sam i skreślij knot ze kerygo żeś wyloz[5]. Wykonej punkt 3 algorytmu.

Algorytm śe kůńczy kej uostańe ino jedyn ńyskrelůny knot. Naszkryflano lista przedstawjo nojkrůtsze drogi dojśćo ze punktu sztartowygo do wszyjskich knotůw we grafje.

Przipisy

  1. Na poczůntku takich ńy bydźe.
  2. Ntp. we pryjszym kroku be to 0+wert kanty.
  3. Nojpjyrw be to ńyskończůność, czyli ńy.
  4. Ntp. przi poczůntku trza půmjyńić ńyskończůność na wert kanty.
  5. Za pjyrszym razym be trza śrkeślić sztartowy knot.