An important aspect of exploratory search over graph data is to understand what
paths connect a given pair of nodes. Since the resulting paths can be manifold,
various works propose ranking paths likely to be of interest to a user; these
methods often rely on enumerating all such paths (up to a fixed length or
number) before ranking is applied. In this paper, we instead propose applying a
shortest path search on weighted versions of the graph in order to directly
compute the most relevant path(s) between two nodes without fixed-length
bounds, further obviating the need to enumerate irrelevant paths. We
investigate weightings based on node degree, PageRank and edge frequency,
contrasting the paths produced by these schemes over the Wikidata graph and
discussing performance issues. Finally we conduct a user study over Wikidata
where evaluators assess the quality of the paths produced; though inter-rater
consensus on which paths are of most interest is low, we achieve statistically
significant results to suggest that users find the weighted shortest paths more
interesting than the baseline shortest paths without weights.