Nejkratší cesty při vyhledávání dopravního spojení

• Thesis title in Czech: Nejkratší cesty při vyhledávání dopravního spojení
• Thesis title in English: Shortest paths when searching for travel connections
• Academic year of topic announcement: 2005/2006
• Thesis type: diploma thesis
• Thesis language: čeština
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: doc. Mgr. Petr Kolman, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 05.01.2006
• Date of assignment: 05.01.2006
• Date and time of defence: 18.09.2007 00:00
• Date of electronic submission: 18.09.2007
• Date of proceeded defence: 18.09.2007
• Opponents: Mgr. Petr Škovroň, Ph.D.

Guidelines

Úkolem diplomanta bude seznámit se s existujícími algoritmy na hledání
nejkratší cesty a prověřit jejich použitelnost (vhodnost) pro aplikaci
vyhledávání dopravního spojení. Diplomant
porovná na reálných (případně náhodných) datech chování různých algoritmů, např.
Dijkstrova algoritmu, heuristických algoritmů, algoritmů asymptoticky
rychlejších než Dijkstrův, algoritmy využívající možnost předzpracování
vstupních dát, algoritmy využívající (skoro) rovinnost prohledávané sítě
(a porovná reálná data s náhodnými),nejlepší algoritmy zpřístupní jako webovou
aplikaci, ve které umožní vyhledávání spojení vzhledem k různým cenovým
(hodnotícím) funkcím a dále umožní flexibilnější zadávání startu a cíle cesty.

References

Uri Zwick: Exact and approximate distances in graphs - a survey;
další články podle zadání školitele