мај месец математике

Алгоритми за најкраћи пут

Један од најпознатијих алгоритама за проналажење најкраћег пута развио је 1959. године Едсгер Дајкстра

Како пронаћи најкраћи пут између две локације? Свакако је најлакше пронаћи упутство преко апликација попут Mapquest или GoogleMap, али њихови програмери су морали да развију алгоритме који ће понудити најпрецизније одговоре ослањајући се, пре свега, на оне који проналазе најмању раздаљину између чворова у графу.

Један од најпознатијих алгоритама ове врсте је Dijkstra алгоритам, који је 1959. године развио холандски информатичар Едсгер Дајкстра. Овај алгоритам у сваком понављању поступка бира тренутно најбоље решење, што би на крају требало да доведе до укупно најбољег решења, односно најкраћег пута.

У оригиналној верзији се путем овог алгоритма проналази најкраћи пут између два чвора у графу, али чешће се користе варијанте у којима се један чвор узима за полазну тачку из које треба пронаћи најкраће путеве ка свим осталим чворовима.

Уколико на мапи града желите да пронађете најкраћи пут између две тачке, овај алгоритам прво раздаљину до ње саме означава вредношћу 0, а затим одређује колико је далека следећа најближа тачка и тако редом тражећи следећи најближи чвор све док не стигне до циља.

Слични алгоритми се не користе само за тражење најближег пута, већ и у неким играма попут Рубикове коцке са најмањим бројем покушаја или за тражења истих глумаца који се појављују у истим филмовима по систему који се ослања на „шест степени сепарације“, односно претпоставку да се помоћу пријатеља својих пријатеља можете повезати са било којом особом у највише шест корака.

Истражите друге текстове:


Grb Republike Srbije
ecsite nsta eusea astc

ЦПН
Улица краља Петра 46
11000 Београд
Република Србија
+381 11 24 00 260
centar@cpn.rs