[Math] Algorithm to find the “optimal” path in a given graph

Question

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy landscape where local minima of $H$ are "valleys" and local maxima are "mountain peaks".

We indicate a path in $G$ from $v$ to $w$ as $\omega: v \to w$ and we denote by $\Phi_{\omega} := \max _{z \in \omega} H(z)$ the maximum height that the path $\omega$ reaches. Given $v,w \in V$, define the energy barrier between $v$ and $w$ by $$\Phi(v,w):= \min_{\omega: v\to w} \Phi_{\omega},$$
where the minimum is taken over all possible paths from $v$ to $w$.

Is there in literature any fast algorithm to find $\Phi(v,w)$? What is the best way to design such algorithm if we need to compute all the energy barriers $\{\Phi(v,w)\}_{v\in V}$ for a fixed target vertex $w$. Is there a clever way to map this problem into one that is well-known, such as shortest path problem on an opportunely modified weighted graph $G'$? Are you aware of any implementation of such optimization problem in software such as Mathematica or Matlab?

Any reference, idea or fruitful comment is welcomed!

(Crossposted on StackExchange since I received no answer).

Answer 1

I think we can transform your problem into a standard shortest-path problem. The key points are

1. The magnitudes of the heights don't matter, just the order (because we want to find the path from $u$ to $v$ with the smallest height). In particular, we can just imagine that all the heights are powers of two, with the ordering the same.
2. If all the heights are powers of two, and we think of these heights as travel costs (lengths of paths), then it is shorter for a path to go through every vertex smaller than $v$ than it is to go through $v$. (Because $2^1 + \dots + 2^{k-1} < 2^k$.) So the shortest path, when heights are powers of two, is the one that goes through the minimum maximum height.

More concretely, sort the heights of the vertices from smallest to largest and map these sorted heights to the list $2^1, 2^2, 2^3, \dots$. Create a new graph where each vertex is labeled by its new height.

Now find the shortest vertex-weighted path from $u$ to $v$ in this new graph. If the length of this path is in $[2^k, 2^{k+1}-1]$, then $\Phi(u,v)$ is equal to the $k$th-smallest height. To see this, note that this shortest path necessarily includes a vertex with new-height $2^k$, but no taller vertices; and there is no path consisting of only shorter vertices, since that path would have length at most $2^k - 1$ (even if it included all vertices with new heights less than $2^k$).

Note you can find the shortest vertex-weighted path by reducing to the standard shortest-path problem. First, make all edges directed and pointing both directions. Make all edges have weight zero. Second, split each vertex $v$ into two vertices, $v_{in}$ and $v_{out}$. Make all the incoming edges of $v$ point to $v_{in}$ and all the outgoing edges point from $v_{out}$. Make an edge pointing from $v_{in}$ to $v_{out}$ with weight equal to the weight of $v$.

We can also use all-pairs shortest paths, etc. Let me know if anything is unclear.