| Title | Algoritmi za pronalaženje najkraćih puteva u mreži i njihova programska implementacija |
| Author | Matej Maligec |
| Mentor(s) | Krešimir Grgić (thesis advisor)
|
| Abstract | 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. |
| Keywords | algorithm graph Dijkstra Bellman-Ford Floyd-Warshall |
| Parallel title (English) | Algorithms for Network Shortest Path Finding and their Software Implementation |
| Committee Members | Krešimir Grgić (committee chairperson)
Drago Žagar (committee member)
Višnja Križanović (committee member)
|
| Granter | Josip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek |
| Lower level organizational units | Department of Communications
Chair of Radiocommunications and Telecommunications |
| Place | Osijek |
| State | Croatia |
| Scientific field, discipline, subdiscipline | TECHNICAL SCIENCES
Electrical Engineering
Telecommunications and Informatics
|
| Study programme type | university |
| Study level | graduate |
| Study programme | Graduate University Study Programme in Electrical Engineering; specializations in: Communications and Informatics, Power Engineering |
| Study specialization | Communications and Informatics |
| Academic title abbreviation | mag.ing.el. |
| Genre | master's thesis |
| Language | Croatian |
| Defense date | 2017-10-04 |
| Parallel abstract (English) | 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. |
| Parallel keywords (Croatian) | algoritam graf Dijkstra Bellman-Ford Floyd-Warshall |
| Resource type | text |
| Access condition | Open access |
| Terms of use |  |
| URN:NBN | https://urn.nsk.hr/urn:nbn:hr:200:926089 |
