Problem najkraćeg puta s jednim izvorom u težinskom usmjerenom grafu

undergraduate thesis

• Title (english): Single Source Shortest Paths in Weighted Directed Graph
• Author: Anto Avgustinović
• Mentor: Andrea Aglić Aljinović (mentor)
• Committee member: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Committee member: Josipa Pina Milišić (član povjerenstva)
• Committee member: Ognjen Dobrijević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2017-09-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Electrical Engineering

Abstract

Problem najkraćeg puta sa jednim izvorom u težinskom usmjerenom grafu pripada matematičkoj grani koja se naziva teorija grafova, a ona pripada diskretnoj matematici. Taj problem je vrlo značajan u matematici, jer se primjenjuje u mnogim problemima u stvarnom svijetu. U ovom radu su prikazani osnovi pojmovi vezani uz graf, te dva algoritma za rješavanje problema navedenog iznad.
Zadnji dio rada je vezan za programsku implementaciju koja rješava problem naveden iznad, pomoću Dijkstrinog ili Bellman-Fordovog algoritma. Shodno tome, izrađena je aplikacija sa pripadajućom programskom potporom, te je prikazan i izgled programa, kao i kratke upute za rad.

Abstract (english)

The problem of the shortest path with one source in the weight-oriented graph belongs to the mathematical branch called the graph theory, and it belongs to the discrete mathematicis. This problem is very important in mathematics, as it applies to many problems in the real world. In this paper, basic terms related to the graph are presented and also two algorithms for solving the problem mentioned above.
The last part of the paper is related to a program implementation that solves the above problem, using the Dijststra or Bellman-Ford algorithm. Consequently, an application with accompanying program support was created, and the layout of the program, as well as short instructions for program operation, were displayed.

• Keywords: težinski usmjereni graf; stabla; najkraći put; Dijkstrin algoritam; Bellman-Fordov algoritam; Python
• Keywords (english): weight-oriented graph; tree; shortest path; Dijkstra algorithm; Bellman-Ford algorithm; Python
• Language: croatian
• URN:NBN: urn:nbn:hr:168:822953
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-13 18:40:55