Path optimization in a DAG: maximizing number of least cost arcs
I've not thought completely through it, but some thoughts on 1) which might be useful:

If you add a constant value k to each edge traversed, you could take into account the number of nodes traversed. In your case, this constant value k should be negative (e.g. the negative value of the maximum edge weight, in your example 11).

Then you might be able to state the following:

The path maximizes the number of least links if $\sum_{i=0}^n (a_i + k)$ &lt; $\sum_{i=0}^m (b_i + k)$.

For your example: (let $P_i$ denote the $i$-th path and $C_i$ denote the costs of path $P_i$)

$P_A=[R, B, S], C_A = -2$

$P_B=[R, A, D, S], C_B = -11$

$P_C=[R, A, C, E, S], C_C = -20$

So $C_C &lt; C_B &lt; C_A$ and hence $P_C$ is your optimal path.

As mentioned, I've not spent too much time to look if there is an example where this approach does not work, but maybe it's a good point to start with.

Of course you get some ties with this approach as well but I think all of these ties are equivalent in the sense that the least cost arcs are traversed and the number of traversed vertices are equivalent. Correct me, if I'm wrong.