Dijkstra Algorithm, Analysis and Applications

Značajan razvoj algoritma pretraživanja usmjerenog grafa nalazimo 50-ih godina prošlog stoljeća. E. W. Dijkstra konstruirao je algoritam na temelju kojeg su kasnije proizašle različite inačice i poopćeni oblici. Svima je zajedničko otkrivanje puta, koji ne mora uvijek biti optimalan. Zbog nedostatka memorije umjesto pretraživanja s jednolikom cijenom, tj. pretraživanja u širinu, možemo koristiti pretraživanje u dubinu. Isto tako, imamo mogućnost kombiniranja prednosti obje vrste algoritma te time dobivamo algoritam iterativnog pretraživanja u dubinu. Svakodnevno se susrećemo s problemom pretraživanja usmjerenog grafa, često ni ne razmišljajući o tome. Prilikom povezivanja na Internet, ili korištenja aplikacije koja sadrži digitalni zapis karte, Dijkstrin algoritam i njegovi oblici, poput algoritma pretraživanja s jednolikom cijenom, osiguravaju nam njihovo nesmetano korištenje. E. W. Dijkstra posvetio je gotovo cijeli svoj život razvoju računarstva i na tome smo mu zahvalni.Significant development of algorithms for finding the shortest paths between nodes in a graph has begun in 1950s. E. W. Dijkstra has conceived an algorithm, on which later on were based many others. All algorithms have in common discovering the path between two nodes, which sometimes is not the optimal one. Because of the lack of memory or computer resource, we prefer to use depth-first search instead of breadth-first search, in case of uniform transition costs. Furthermore, we can combine the benefits from each algorithm and therefore use iterative search in depth. Finding the shortest path is almost an everyday problem. For an example, it is used when we connect to the Internet or when we want to find directions on digital map. In these cases, uniform-cost search algorithm does all the work in the background. E. W. Dijkstra has dedicated his whole life to computer science and its development and we are very thankful for that