Motohiro Ohkura

A railway fare for a specific path is usually determined by the distance, i.e. the longer the distance, the higher the fare. The fare rate, however, is sometimes different by area even within the same railway company. In addition, many of companies have additional rules to be used in the fare calculation, e.g. discounts for specific paths. In order to calculate the fare between a given pair of stations, we have to find the minimum cost path, but the shortest path (in the physical sense) is not always the minimum cost path for the reasons mentioned above. In the past, most of the efforts have been focused on an enumeration of feasible paths between a pair of stations and a comparison of their resulting fares in order to choose the minimum fare for the pair. This approach has inevitably led to a problem of a very large computational time. In this paper, we propose a much more efficient algorithm which basically uses the Dijkstra's algorithm with a modification which reflects the existence of a set of subnetworks which have their own fare rates. Our algorithm dramatically reduces the computational time, because the algorithm need not enumerate a large number of paths for every pair of stations.