Computer vision and machine learning tasks can be modelled as the inference problems in an MRF-MAP formulation and can be reduced to minimizing a submodular function.
Input to the Most Navigable Path (MNP) problem consists of the following: (a) a road network represented as a directed graph, where each edge is associated with numeric attributes of cost and “navigability score” values; (b) a source and a destination and; (c) a budget value which denotes the maximum permissible cost of the solution.