Thesis Details

Nejkratší cesty v grafu

Master's Thesis Student: Krauter Michal Academic Year: 2008/2009 Supervisor: Masopust Tomáš, RNDr., Ph.D.
English title
Shortest Paths in a Graph
Language
Czech
Abstract

This thesis deals with shortest paths problem in graphs. Shortest paths problem is the basic issue of graph theory with many pracitcal applications. We can divide this problem into two following generalizations: single-source shortest path problem and all-pairs shortest paths problem. This text introduces principles and algorithms for generalizations. We describe both classical and new more efficient methods. It contains information about how some of these algorithms were implemented and offers an experimental comparison of these algorithms.

Keywords

Shortest paths, graph algorithms, single-source shortest path problem, all-paris shortest path problem, Dijkstra's algorithm, Bellman-Ford's algorithm, Floyd-Warshall's algorithm.

Department
Department of Information Systems FIT BUT
Degree Programme
Information Technology, Field of Study Information Systems
Files
Status
defended, grade B
Date
27 February 2009
Reviewer
Křivka Zbyněk, Ing., Ph.D.
Committee
Švéda Miroslav, prof. Ing., CSc. (DIFS FIT BUT), předseda
Burget Radek, doc. Ing., Ph.D. (DIFS FIT BUT), člen
Češka Milan, prof. RNDr., CSc. (DITS FIT BUT), člen
Kreslíková Jitka, doc. RNDr., CSc. (DIFS FIT BUT), člen
Rogalewicz Adam, doc. Mgr., Ph.D. (DITS FIT BUT), člen
Sochor Jiří, prof. Ing., CSc. (FI MUNI), člen
Citation
KRAUTER, Michal. Nejkratší cesty v grafu. Brno, 2009. Master's Thesis. Brno University of Technology, Faculty of Information Technology. 2009-02-27. Supervised by Masopust Tomáš. Available from: https://www.fit.vut.cz/study/thesis/7245/
BibTeX 
@mastersthesis{FITMT7245,
    author = "Michal Krauter",
    type = "Master's thesis",
    title = "Nejkrat\v{s}\'{i} cesty v grafu",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2009,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/7245/"
}

Theses

Back to top