Note

The maximum weight path problem between two given vertices $s$ (source) and $t$ (target) in a graph $G$ is the problem of finding a simple path of maximum weight in a given graph. A path is called simple if it does not have any repeated vertices; the weight of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges.

Note

The maximum weight of $K$ paths problem between two given vertices $s$ and $t$ in a graph $G$ is the problem of finding a $K$ distinct, simple paths between nodes $s$ and $t$ maximizing the sum of the weight of $K$ paths.