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

završni rad

• Naslov (engleski): Single Source Shortest Paths in Weighted Directed Graph
• Autor: Anto Avgustinović
• Mentor: Andrea Aglić Aljinović (mentor)
• Član povjerenstva: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Član povjerenstva: Josipa Pina Milišić (član povjerenstva)
• Član povjerenstva: Ognjen Dobrijević (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2017-09-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Elektrotehnika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: težinski usmjereni graf; stabla; najkraći put; Dijkstrin algoritam; Bellman-Fordov algoritam; Python
• Ključne riječi (engleski): weight-oriented graph; tree; shortest path; Dijkstra algorithm; Bellman-Ford algorithm; Python
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:822953
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-03-13 18:40:55