Diplomová práce

Porovnanie algoritmov pre testovanie existencie najkratších ciest

Shortest-path Feasibility Algorithms: An Evaluation

Bc. Matúš Galba
Anotace

Problém existencie najkratších ciest je definovaný pre orientované grafy s ohodnotením hrán. Úlohou je nájsť v grafe cyklus zápornej dĺžky alebo poskytnúť dôkaz o jeho neexistencii vo forme prípustnej potenciálovej funkcie. Cieľom tejto práce je predstaviť algoritmy pre riešenie problému existencie najkratších ciest jednotným spôsobom. Súčasťou tejto práce je implementácia predstavených algoritmov a ich experimentálne overenie na vytvorenej testovacej sade.

Abstract

The shortest path feasibility problem is defined for directed graphs with weighted edges. The task is to find a cycle of negative length in the graph or to provide proof of its non-existence in the form of a feasible set of potentials. The aim of this work is to present algorithms for solving the shortest path feasibility problem in a unified way. Part of this work is dedicated to the implementation of the algorithms presented and their experimental evaluation on a created test set.

Klíčová slova
algoritmy problém existencie najkratších ciest detekcia záporných cyklov relaxácia hrán
Zadání práce
Problém existence nejkratších cest (SPF) je definován pro orientované, hranově ohodnocené grafy. Úkolem je najít v grafu cyklus záporné délky resp. poskytnout důkaz (přípustnou potenciálovou funkci) o jeho neexistenci. Problém SPF je v úzkém vztahu k problému nejkratších cest (SSSP): řešení problému SSSP je i řešením problému SPF. Naopak, přípustnou potenciálovou funkci lze využít k rychlému řešení problému SSSSP. Pro řešení problému SPF je k dispozici celá řada různých algoritmů, které jsou založeny na tzv. relaxaci hran. Přehledový článek Shortest-path Feasibility Algorithms: An Experimental Evaluation z roku 2002 představuje základní přístupy k řešení SPF problému. Od roku 2002 byly publikovány další přístupy k řešení problému nejkratších cest. Cílem práce je představit algoritmy pro řešení SPF jednotným způsobem, včetně pseudokódu. Součástí práce je implementace algoritmů a experimentální ověření a srovnání různých přístupů (zejména ve srovnání s výsledky experimentů publikovaných v citovaném přehledovém článku).
Administrativní informace
Práce zkontrolována:
18. 12. 2023 08:52, prof. RNDr. Ivana Černá, CSc., učo 1419
Plný text práce
1,4 MB / soubor PDF
Přílohy (1)
Jazyk práce
slovenština slovenština
Termín obhajoby
14. 2. 2024
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Ivana Černá, CSc., učo 1419
KTP FI MU

Oponent

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Kvantové a jiné neklasické výpočetní modely

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.