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.

Improve this question
$\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$
    – Max Alekseyev
    Commented 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$
    – Manfred Weis
    Commented 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$
    – Max Alekseyev
    Commented Apr 28, 2018 at 12:00

1 Answer 1

Reset to default
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.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .