I've got the following problem.I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$.The optimal path has to maximize the number of least cost arcs.In the example:R->B->S is the least cost path but it's not the optimal.R->-A->D->S costs less than R->A->C->E->S , but the latter is the optimum as it goes through more, least cost arcs.My current problem, which constitute the object this question, is to find a way of defining formally how to compare two paths according to my intuitive understanding, as comparing them comes before choosing the optimal one.Of two paths, the better one is the one that traverses the highest number of least cost arcs.I have been considering three ways, some that seem not fully adequate for my purpose, but would welcome other suggestions.My three  ideas are the following:Minimizing the average of the cost of arcs on the path. Minimizing the average is not fully ok: imagine to have a path with cost [3,12], and a path with cost [3,10,10]. The average of the first path is less than the average of the second, but the second is the optimal as it traverses more paths.Comparing individually the arcs of the pathsGiven two paths $A$ and $B$:Let $A$ = [$a_1,\ldots,a_n$] and $B$ = [$b_1,\ldots,b_m$] where $a_i$ and $b_i$ are the arc costs of $A$ and $B$ respectively.Then $A$ is better than $B$ if $\sum_{i=0}^n card(B < a_i)$ <  $\sum_{i=0}^m card(A < b_i)$ where $card$ represents the cardinality of the set, and $B < a_i$ is defined as $\{b_j  \in B \mid b_j < a_i\}$, the comparison being on the weight of the concerned arcs.However, with this second approach I get many ties between different paths, increasing the risk of getting a suboptimal path.Comparing the min-max of the arcs weights for each path.Another possibility is to compute the min-max of the arcs of each path, and choose the smaller one. It is intrinsically different from the other approaches.But it is  not fully what I seek to achieve.For example, min-max over [1,1,1,3] and [2,2,2,2] chooses the latter one, while the best one is the first.To motivation behind my intuition is the following: each node is a checkpoint that the solution may traverse on its way from the node $R$ to node $S$. The goal is to output a sequence $Q$ with an associated precisionif the chosen path is R->A->D->S, then $\;Q\;$ is $\;\;$A $\pm$ 10, D $\pm$ 5, S $\pm$ 7Clearly, the optimal solution has to be as precise as possible, so the optimal path has to emit the maximum number of least cost arcs.Once the comparison of paths has been formalized precisely, my problem will be to compute the optimal path on a given graph. But right now the  question is only to find a proper way of comparing paths. The role of the graph structure is only, possibly, to help convey the intuition of my problem.
Path optimization in a DAG: maximizing number of least cost arcs
algorithms;graph traversal;weighted graphs;partial order;order theory