Vizualizacija algoritmov za iskanje najkrajših poti na grafih

KLIČKOVIĆ, SANJA (avtor), Fürst, Luka (mentor)

V diplomski nalogi predstavljamo interaktivno aplikacijo, ki vizualizira delovanje nekaterih algoritmov za iskanje najkrajših poti na grafih. Iz precej širokega nabora algoritmov smo izbrali Dijkstrov, Bellman-Fordov, Floyd-Warshallov, D'Esopo-Papeov in Fredman-Tarjanov algoritem. V besedilu teoretično predstavljamo njihovo delovanje in uporabo na različnih področjih, navajamo pa tudi njihovo psevdokodo. Predstavljamo tudi delovanje aplikacije in primere delovanja za posamezne algoritme. Aplikacijo smo izdelali kot didaktički pripomoček, namenjen tako učiteljem kot študentom.

• Jezik: Slovenski jezik
• Ključne besede: vizualizacija, algoritem, graf, najkrajša pot, iskanje poti v grafu, Dijkstra, Bellman-Ford, Floyd-Warshall, D'Esopo-Pape, Fredman-Tarjan, didaktički pripomoček
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2021
• PID: 20.500.12556/RUL-124843
• COBISS.SI-ID: 53043715
• Datum objave v RUL: 23.02.2021

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Visualization of algorithms for finding shortest paths in graphs

Izvleček

In this diploma thesis, we present an interactive application for visualizing algorithms for finding shortest paths in graphs. From a fairly large set of algorithms, we selected the Dijkstra, Bellman-Ford, Floyd-Warshall, D'Esopo-Pape, and Fredman-Tarjan algorithm. We describe them informally and in pseudocode. Tha application was designed as a didactic tool, both for teachers and for students.

• Ključne besede: visualization, algorithm, graph, shortest path, finding path in graph, Dijkstra, Bellman-Ford, Floyd-Warshall, D'Esopo-Pape, Fredman-Tarjan, didactic tool