0
$\begingroup$

I am looking for a graph-theoretic algorithm, that determines among all simple paths $\mathcal{P}_{ab}$ that connect vertex $a$ with vertex $b$ the one, that has minimal average edge-length, i.e. $$\ p_{ab}\in\mathcal{P}_{ab}:\quad \frac{\ell(p_{ab})}{\mathrm{card}(p_{ab})} \le \frac{\ell(q_{ab})}{\mathrm{card}(q_{ab})},\; \forall q_{ab}\in\mathcal{P}_{ab}$$

By "graph-theoretic" I mean algorithms in the vein of those that are likely to be found in publications about algorithmic graph-theory; on the contrary, mathematical programming is not what I am looking for.

$\endgroup$
3
  • 1
    $\begingroup$ Using dynamic programming, one can find a shortest path between $a$ and $b$ with a fixed number of edges $k$ (for all values of $k$). It remain to divide the length of each such path by the corresponding $k$, and pick the one with the smallest ratio. $\endgroup$ Apr 27, 2018 at 22:01
  • $\begingroup$ @MaxAlekseyev dynamic programming would have been an option, if simplicity of the reported paths were guaranteed. It is however an option to filter out all non-simple paths to find an upper bound on the optimal solution. $\endgroup$ Apr 28, 2018 at 6:40
  • $\begingroup$ Non-simple paths do not pose a trouble for dynamic programming in this case (since it looks for paths with fixed number of edges). The trouble may come from existence of short cycles, which may need to be taken infinitely many times along a path from $a$ to $b$ to get the average edge length down to the minimum. So, besides finding finite paths, one has to explore cycles to determine whether the minimum is achieved on infinite paths. $\endgroup$ Apr 28, 2018 at 12:00

1 Answer 1

1
$\begingroup$

A practical algorithm would be to grow two minimum spanning trees that are rooted in start- and endnode in the following manner:

Preprocessing:

  • assign to start-vertex $a$ label $\alpha$, to end-vertex $b$ label $\beta$ and label $\gamma$ to all other vertices.
  • sort the edges in ascending order of lengths

Iteration:

  • add to the path between $a$ and $b$ the shortest edge whose adjacent vertices' labels aren't equal
    • if the labels are $\alpha$ and $\beta$ the path of least average edge-length has been found and the iteration is terminated
  • assign to the edges' vertex that is labeled $\gamma$ the label of the other adjacent vertex and continue

Postprocessing:

recursively delete from the path-graph that, has been generated in the iteration, all edges that are adjacent to a vertex of degree $1$ unless that vertex is $a$ or $b$


That algorithm grows two minimum spanning trees via Prim's algorithm until they are connected.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.