# Path optimization in a DAG: maximizing number of least cost arcs

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:

1. 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.

2. Comparing individually the arcs of the paths

Given 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.

3. 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 "precision"

if the chosen path is R->A->D->S, then $\;Q\;$ is $\;\;$A $\pm$ 10, D $\pm$ 5, S $\pm$ 7

Clearly, 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.

• Note that, in the special case where all edges have the same cost, you're trying to find the longest path between two vertices, which is NP-hard. As such, you shouldn't expect there to be an efficient algorithm for the general problem. – David Richerby May 26 '15 at 7:13
• @DavidRicherby : $\;\;\;$ How is that shown? $\:$ (Is it by using a definition of "path" that either doesn't allowing revisiting vertices or doesn't allow retracing edges?) $\;\;\;\;\;\;\;\;$ – user12859 May 26 '15 at 10:40
• @DavidRicherby according to the definition (with ∑ and unusual notations $B<a_i$), if all edges have the same cost, all paths are equivalent since their associated conmparative values are 0. If he had used "≤" rather than "<", then these values would be |B|×|A|. and all paths would still be equivalent. So your conclusion may be right, but it requires more to be established,. – babou May 26 '15 at 10:48
• Am I correct in interpreting $B<a_i$ as $\{b_j\in B\mid b_j<a_i\}$ ? – babou May 26 '15 at 10:58
• I edited your question so as to clarify as much as I can, and remove the second part (only one problem in a question). I also tried to remain compatible with existing answers, - - - It is not yet clear what you are after. You should give us a brief example of the real problem you are working on, because we will never get your intuition otherwise. Where do these approximations come from? What do they mean? What really happens on an arc of the graph (some kind of unprecise processing step?) What is the process you want to optimize? Give us the real problem, not your vision. – babou May 31 '15 at 16:03

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)$ < $\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 < C_B < 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.

The question is proposing 3 definitions for comparing paths. The first and third are apparently not satisfactory for the author of the question. We show that the second definition is not usable either.

The second formalization seems more sophisticated, and is precisely given. It is not a metric but the definition of a "better" relation between paths, that is noted here "$\prec$".

$$A\prec B\;\;\;\mbox{ iff }\;\;\;\sum_{i=0}^n |B < w(a_i)| < \sum_{i=0}^m |A < w(b_i)|$$ where $w(a)$ is the weight of an arc $a$,
and $B < w(a_i)$ is defined as $\{b_j \in B \mid w(b_j) < w(a_i0\}$

Actually, this can be redefined, I think more intuitively, as it helped me find the example below, as:

\begin{align} A\prec B\;\;\text{ iff }\;\;|\{(a_i,b_j)\mid a_i\in A, b_j\in& B, w(b_j)<w(a_i)\}|\;<\; \\ &|\{(a_i,b_j)\mid a_i\in A, b_j\in B, w(b_j)>w(a_i)\}| \end{align}

However, the problen is that this relation is not an order on paths, not even a preorder, since it is not transitive:

A counter example is given by the following three paths, here just given as sets of weights:

$$A=\{9,5,4\},\;\;\; B= \{6\},\;\;\; C= \{8,7,3\}$$

It is easily verified that

$$A\prec B,\;\;\; B\prec C,\;\;\; C\prec A$$

Thus, despite the notation chosen here, the relation $\prec$ cannot be used to order solutions. Hence this relation cannot be used to define the choice of an optmal path, independently of how paths are defined or the graph explored.

None of the three modes of comparison seems to meet the need of the author of the question. The motivation given by the author for his intuition is too vague to help. A full example of the real problem he is adressing should be given to have a chance for further progress.

• Thank for your time and effort. You pointed out correctly the problem: I'm still trying to define what makes a path better than another one. I edited the question in the final part of the question – Charles G. May 28 '15 at 14:49
• Thank you. So I should just ask for a proper definition of "optimal"? – Charles G. May 28 '15 at 15:14