Experimentální analýza algoritmů pro hledání nejkratších cest

• Thesis title in Czech: Experimentální analýza algoritmů pro hledání nejkratších; cest
• Thesis title in English: Experimental analysis of shortest paths algorithms
• Academic year of topic announcement: 2005/2006
• Thesis type: diploma thesis
• Thesis language: čeština
• Department: Department of Software Engineering (32-KSI)
• Supervisor: RNDr. Alena Koubková, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 04.11.2005
• Date of assignment: 04.11.2005
• Date and time of defence: 25.05.2009 00:00
• Date of electronic submission: 25.05.2009
• Date of proceeded defence: 25.05.2009
• Opponents: Mgr. Martin Mareš, Ph.D.

Guidelines

Úkolem diplomanta bude vypracovat experimentální studii o chování algoritmů pro hledání nejkratších cest v grafu podle zásad experimentální algoritmiky, s využitím vlastních nebo volně dostupných implementací a programových prostředků pro generování vstupních dat, testování algoritmů a zpracování výsledků experimentů. Součástí práce bude přehled a popis známých algoritmů na hledání nejkratších cest včetně uvedení teoretických výsledků o jejich složitosti a výsledků předchozích experimentálních studií, pokud existují.

References

B. V. Cherkassky, A. V. Goldberg, T. Radzik: Shortest paths algorithms: theory and experimental evaluation. Math. Programming 73 (1996), 129 - 174.

U. Meyer: Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds. Journal of Algorithms 48 (2003), 91 - 134.

B. M. E. Moret: Towards a discipline of experimental algorithmics. DIMACS series in Discrete Math. and Theoret. Computer Science 59 (2002), 197 - 213.