Algorithms for Network Shortest Path Finding and their Software Implementation

Algoritmi za pronalaženje najkraćih puteva u mreži vrlo su bitni za brz i pouzdan prijenos podataka od početne to krajnje točke u mreži. Neki od tih algoritama su Dijkstrin, Bellman-Fordov i Floyd-Warshallov algoritam. Dijkstrin algoritam radi samo sa pozitivnim težinskim vrijednostima grana, dok Bellman-Fordov i Floyd-Warshallov algoritam mogu raditi i sa negativnim vrijednostima. Kod Bellman-Fordovog algoritma može doći do detekcije negativnog ciklusa, što znači da se vrijednost najkraćeg puta do određenog čvora može beskonačno smanjivati. Ukoliko negativan ciklus ne postoji, Dijkstrin i Bellman-Fordov algoritam imaju slično vrijeme izvođenja, dok Floyd-Warshallov algoritam ima najveće vrijeme izvođenja zbog prikaza izlaznih vrijednosti u obliku matrice te velikog broja mogućih međurješenja.Shortest path algorithms are very important for fast and reliable data transportation from a starting to an ending point in a network. Some of these algorithms are Dijkstra's, Bellman-Ford's and Floyd-Warshall's algorithm. Dijkstra's algorithm works only with positive edge weights, whereas Bellman-Ford's and Floyd-Warshall's algorithms are able to work with negative edge weights aswell. Bellman-Ford's algorithm is capable of negative cycle detection, which means that the shortest path value to a specific vertex can be infinitely reduced. If there is no such cycle, Dijkstra's and Bellman-Ford's algorithms have a similar runtime, while Floyd-Warshall's algorithm has the greatest runtime of the three, because of the format of the output values being a data matrix and a large amount of possible intermediate solutions