  The landscape of applications and subroutines relying on shortest path
computations continues to grow steadily. This growth is driven by the
undeniable success of shortest path algorithms in theory and practice. It also
introduces new challenges as the models and assessing the optimality of paths
become more complicated. Hence, multiple recent publications in the field adapt
existing labeling methods in an ad-hoc fashion to their specific problem
variant without considering the underlying general structure: they always deal
with multi-criteria scenarios and those criteria define different partial
orders on the paths. In this paper, we introduce the partial order shortest
path problem (POSP), a generalization of the multi-objective shortest path
problem (MOSP) and in turn also of the classical shortest path problem. POSP
captures the particular structure of many shortest path applications as special
cases. In this generality, we study optimality conditions or the lack of them,
depending on the objective functions' properties. Our final contribution is a
big lookup table summarizing our findings and providing the reader an easy way
to choose among the most recent multicriteria shortest path algorithms
depending on their problem's weight structure. Examples range from
time-dependent shortest path and bottleneck path problems to the fuzzy shortest
path problem and complex financial weight functions studied in the public
transportation community. Our results hold for general digraphs and therefore
surpass previous generalizations that were limited to acyclic graphs.
