Abstract. Millions of users rely on navigation applications to compute an optimal route for their trips. The basic functionality of these applications is to find the minimum cost route between a source and target node in the transportation network. In this paper, we address a variant of this problem, where the computed route is required to contain a set of Points of Interest of specific types. Our approach is based on the concept of keyword skyline. We formally define this concept, and we show how to compute the keyword skyline for the vertices of a given network and how to use it for computing the shortest keyword covering paths. We present different variants of this method, including an approximation algorithm, providing different trade-offs between preprocessing cost and execution time. Finally, we present an experimental evaluation of our approach using real-world datasets of different sizes, including also a comparison to the current state-of-the-art algorithm for this problem.