  Searching for optimal ways in a network is an important task in multiple
application areas such as social networks, co-citation graphs or road networks.
In the majority of applications, each edge in a network is associated with a
certain cost and an optimal way minimizes the cost while fulfilling a certain
property, e.g connecting a start and a destination node. In this paper, we want
to extend pure cost networks to so-called cost-gain networks. In this type of
network, each edge is additionally associated with a certain gain. Thus, a way
having a certain cost additionally provides a certain gain. In the following,
we will discuss the problem of finding ways providing maximal gain while
costing less than a certain budget. An application for this type of problem is
the round trip problem of a traveler: Given a certain amount of time, which is
the best round trip traversing the most scenic landscape or visiting the most
important sights? In the following, we distinguish two cases of the problem.
The first does not control any redundant edges and the second allows a more
sophisticated handling of edges occurring more than once. To answer the maximum
round trip queries on a given graph data set, we propose unidirectional and
bidirectional search algorithms. Both types of algorithms are tested for the
use case named above on real world spatial networks.
