Pregled algoritama za traženje najkraćeg puta u grafu

završni rad

• Naslov (engleski): Overview of Algorithms for Shortest Path Problem
• Autor: Salim Žunić
• Mentor: Juraj Fosin (mentor)
• Član povjerenstva: Ivan Grgurević (predsjednik povjerenstva)
• Član povjerenstva: Zvonko Kavran (član povjerenstva)
• Član povjerenstva: Tonči Carić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet prometnih znanosti; (Inteligentni transportni sustavi i logistika); (Zavod za inteligentne transportne sustave); Zagreb
• Datum i država obrane: 2018-09-17, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Tehnologija prometa i transport; Poštansko-telekomunikacijski promet

Sažetak

U ovom radu prikazati će se pregled algoritama za traženje najkraćeg puta u grafu. Prikazani su Dijsktrin algoritam i Floyd-Warshallov algoritam, te su objašnjeni na primjerima manjih grafova. U prvom dijelu rada objašnjena je definicija grafova, osnovni načini prikaza grafova, te njihova osnovna podjela. Implementiran je Dijkstrin algoritam u programskom jeziku Java. Program je napravljen u razvojnom okruženju InteliJ. Algoritam je implementiran na primjeru grafa koji se sastoji od osam čvorova i simbolizira manju prometnu mrežu u informacijsko komunikacijskom prometu. Čvorovi grafa predstavljaju usmjerivače (engl. Router). Cilj programa je izračunati najmanje moguće količine kašnjenja od početnog čvora, do ostalih čvorova u mreži, odnosno grafu. Usmjeravanje u Internet prometu je proces pronalaženja puta kojim će se slati paketi od izvorišnog usmjerivača do odredišta. Cilj je da paketi na odredište stignu što brže, te se pri odlučivanju koriste algoritmi za traženje najkraćeg puta, poput Dijkstrinog algoritma implementiranog u ovom radu.

Sažetak (engleski)

This paper presents overview of algorithms for the shortest path problem. It explains Dijkstra algorithm and Floyd-Warshalls algorithm that are explained on examples of smaller graphs. Definition of graphs, basic methods of graph presentation and their basic division are explained in fist part of the paper. Dijkstra algorithm is implemented in Java programing language. Program was made in InteliJ development environment. Algorithm is implemented on the example of graph which is made of eight nodes. Graph symbolizes smaller information and communication traffic network. Goal of program is to calculate delays from source node to all other nodes in network. Routing, in Internet traffic, is the process of choosing a path over which to send packets from source router to destination. Goal is for packets to be delivered as soon as possible, for decision making we are using shortest path algorithms as Dijsktra algorithm implemented in this paper.

• Ključne riječi: Java; Graf; Dijkstrin algoritam; Problem najkraćeg puta
• Ključne riječi (engleski): Java; Graph; Dijkstra algorithm; Shortest path problem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:119:367599
• Studijski program: Naziv: Promet; smjerovi: Cestovni, Željeznički, Vodni, Zračni, Poštanski, Informacijsko-komunikacijski, Gradski; Smjer: Informacijsko-komunikacijski; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka prometa (univ. bacc. ing. traff.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2018-09-20 16:48:07