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

undergraduate thesis

• Title (english): Overview of Algorithms for Shortest Path Problem
• Author: Salim Žunić
• Mentor: Juraj Fosin (mentor)
• Committee member: Ivan Grgurević (predsjednik povjerenstva)
• Committee member: Zvonko Kavran (član povjerenstva)
• Committee member: Tonči Carić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Transport and Traffic Sciences; (Division of Intelligent Transport Systems and Logistics); (Department of Intelligent Transport Systems); Zagreb
• Defense date and country: 2018-09-17, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Traffic and Transport Technology; Postal and Telecommunications Traffic

Abstract

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.

Abstract (english)

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.

• Keywords: Java; Graf; Dijkstrin algoritam; Problem najkraćeg puta
• Keywords (english): Java; Graph; Dijkstra algorithm; Shortest path problem
• Language: croatian
• URN:NBN: urn:nbn:hr:119:367599
• Study programme: Title: Traffic and Transport; specializations in: Road Traffic and Transport, Railway Traffic and Transport, Water Traffic and Transport, Air Traffic and Transport, Postal Traffic, Information and Communication Traffic, Urban Traffic and Transport; Course: Information and Communication Traffic; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka prometa (sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka prometa)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2018-09-20 16:48:07