  Graphs have been commonly used to model many applications. A natural problem
which abstracts applications such as itinerary planning, playlist
recommendation, and flow analysis in information networks is that of finding
the heaviest path(s) in a graph. More precisely, we can model these
applications as a graph with non-negative edge weights, along with a monotone
function such as sum, which aggregates edge weights into a path weight,
capturing some notion of quality. We are then interested in finding the top-k
heaviest simple paths, i.e., the $k$ simple (cycle-free) paths with the
greatest weight, whose length equals a given parameter $\ell$. We call this the
\emph{Heavy Path Problem} (HPP). It is easy to show that the problem is
NP-Hard.
  In this work, we develop a practical approach to solve the Heavy Path problem
by leveraging a strong connection with the well-known Rank Join paradigm. We
first present an algorithm by adapting the Rank Join algorithm. We identify its
limitations and develop a new exact algorithm called HeavyPath and a scalable
heuristic algorithm. We conduct a comprehensive set of experiments on three
real data sets and show that HeavyPath outperforms the baseline algorithms
significantly, with respect to both $\ell$ and $k$. Further, our heuristic
algorithm scales to longer lengths, finding paths that are empirically within
50% of the optimum solution or better under various settings, and takes only a
fraction of the running time compared to the exact algorithm.
