Prihlásenie

Predkladaná dizertačná práca sa zaoberá problémami trasovania v rozsiahlej dopravnej sieti. Cieľom práce je implementovať, porovnať a vyhodnotiť rôzne známe algoritmy na hľadanie najkratšej cesty a ich variácie a navrhnúť vlastný rýchly algoritmus na nájdenie najkratšieho prípustného sledu v orientovanom grafe. Prípustný sled je taký sled (trasa v dopravnej sieti), ktorý rešpektuje dodatočné podmienky v modelovanej realite – zakázané manévre (odbočenia, otočenia) v dopravnej sieti. Klúčové slová: dopravná sieť, orientovaný graf, najkratšia cesta, zakázaný manéver

This thesis deals with the shortest path problems in extensive transport network. One of the objectives of this work is to implement, compare and summarize well known shortest path algorithms and their modifications. The main focus is to design a fast algorithm for finding the feasible shortest trail in a directed graph. Feasible trail is such a route in transport network, which respects the additional terms in the modeled reality – prohibited maneuvers (e.g. left-turn, U-turn) in the transport network. Keywords: transport network, directed graph, shortest path, prohibited meneuver