Naslov
Najbrži poznati algoritmi za pronalaženje najkraćih puteva u planarnim grafovima
(The fastest known shortest paths algorithm for planary graphs)

Autori
Škugor, Ivan

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, diplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
10.09

Godina
2010

Stranica
50

Mentor
Hlupić, Nikica

Ključne riječi
graf; najkraći put; algoritam
(graph; shortest path; algorithm)

Sažetak
Ukratko opisati problematiku i povijesni razvoj algoritama za traženje najkraćih puteva u grafu, a podrobnije analizirati Dijkstrin algoritam kao najopćenitije rješenje. Potom ukazati na osobitosti planarnih grafova koje čine teorijsku osnovu algoritama za traženje najkraćih puteva u njima brže nego Dijkstrinim algoritmom. Podrobno opisati jedan ubrzani algoritam za planarne grafove te isprogramirati u C# ili C++ manju aplikaciju za ilustraciju njegovog rada. Teorijski i eksperimentalno usporediti brzinu tog i Dijkstrinog algoritma. Na kraju ukratko navesti i ideje drugačijih algoritama te njihove možebitne prednosti i nedostatke u odnosu na odabrani.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA