izpis_h1_title_alt

Najkrajše poti z enim virom v dinamičnih grafih
ID Prošek, Anže (Avtor), ID Fürst, Luka (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (1,40 MB)
MD5: 77829E30A7F863AE24358A8AACE0BFB1

Izvleček
Iskanje najkrajših poti z enim virom v uteženih grafih je klasičen problem na področju algoritmov in podatkovnih struktur. Ta problem lahko rešujemo z znanim Dijkstrovim algoritmom. V diplomski nalogi pa obravnavamo različico problema, pri kateri se v vsakem koraku lahko spremeni teža neke povezave grafa, lahko pa se povezava tudi doda ali odstrani. Seveda lahko problem rešimo tako, da po vsaki spremembi poženemo Dijkstrov algoritem, vendar pa obstajajo tudi učinkovitejši pristopi. V okviru diplomske naloge se ukvarjamo s t.i. inkrementalnim in dekrementalnim algoritmom: prvi obravnava vstavljanje nove povezave in znižanje teže obstoječe povezave, drugi pa odstranjevanje in zvišanje teže obstoječe povezave. Oba algoritma smo implementirali in preizkusili z različnimi testnimi scenariji.

Jezik:Slovenski jezik
Ključne besede:Graf, dinamični graf, Dijkstra, algoritem, inkrementalni, dekrementalni
Vrsta gradiva:Diplomsko delo/naloga
Tipologija:2.11 - Diplomsko delo
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2024
PID:20.500.12556/RUL-160512 Povezava se odpre v novem oknu
COBISS.SI-ID:208529667 Povezava se odpre v novem oknu
Datum objave v RUL:29.08.2024
Število ogledov:154
Število prenosov:41
Metapodatki:XML DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Single-Source Shortest Paths in Dynamic Graphs
Izvleček:
Finding the shortest paths from a single source in weighted graphs is a classic problem in the field of algorithms and data structures. This problem can be solved using Dijkstra's algorithm. However, in this thesis, we deal with a version of the problem in which the graph can be continuously updated. In particular, in each step, one of the edge weights can be modified, or an edge can be added or removed. Of course, we could run Dijkstra's algorithm after each update, but there are also more efficient approaches. In the thesis, we describe the so-called incremental and decremental algorithms; the former handles edge insertions and weight decreases, and the latter deals with edge removals and weight increases. We implemented both algorithms and tested them using different test scenarios.

Ključne besede:Graph, dynamic graph, Dijkstra, algorithm, incremental, decremental

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj