| Popis: |
We deal with algorithms for finding cheapest connections in a transportation network with timetables where a cheapest connection is one with the lowest value given some evaluation function. A problem of cheapest connection in a transportation network is introduced and formalized, and is reduced to a shortest path problem in a directed graph. A representation of a transportation network by a directed graph is thereafter given, and several standard algorithms for the shortest path problem are described in turn. Several optimizations of the algorithms for their application to the transportation network are proposed. Eventually, performance results of the algorithms are presented along with their comparison. The algorithms were tested on (1) the train network of the Czech Republic, and on (2) a randomly generated graph. |
