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.

Answer 2

$\Phi(v,w) \le h$ if there is a path from $v$ to $w$ in the graph obtained from $G$ by removing all vertices of height $> h$. Moreover, the maximum height of any path in this graph from $v$ to $w$ gives you an upper bound $\le h$ on $\Phi(v,w)$. So for a given $v$ and $w$ it is easy to compute $\Phi(v,w)$, at least to a fixed precision, using a binary search on $h$. Of course since there are only a finite number of $H$ values, when the precision is high enough you know $\Phi(v,w)$ exactly.

If you want all $\Phi(v,w)$ for fixed $w$, you can do something like this. For each $v$ we will have lower bound $L_n(v)$ and upper bound $U_n(v)$ at step $n$ of our process: initially each $L_0(v)$ is the minimum of all heights and $U_0(v)$ is the maximum of all heights. For convenience, let's scale $H$ so that the minimum is $0$ and the maximum is $H$. We will have $H_n(v) - L_n(v) \le 2^{-n}$. Let $S_n$ be the set of all lower bounds $L_n(v)$ for vertices $v$ whose $\Phi$ values are still in question. For each $s \in S_n$, let $t$ be the maximum of $U_n(v)$ for those $v$ with $L_n(v) = s$ (so $t \le s + 2^{-n}$). If there are no $H$ values in the interval $[s, t)$, then we know $\Phi(v,w) = t$ for all these $v$ (and we can remove them from further consideration). Otherwise, let $h = (s+t)/2$. Then by looking at the graph obtained by removing vertices with height $>h$, each of these vertices gets either $L_{n+1}(v) = h$ or $U_{n+1} \le h$.

Answer 3

There is quite a large literature on shortest paths on polyhedral surfaces, where the distance function is either Euclidean distance or more general metrics. For example, this recent paper extends to convex distance functions:

Cheng, Siu-Wing, and Jiongxin Jin. "Shortest paths on polyhedral surfaces and terrains." Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM, 2014. (ACM link)

Here's an example I made with a student (Biliana Kaneva) finding all shortest paths on a terrain (overhead view) from one vertex to every other vertex:

---

       

---

One can almost see runoffs and rivers—terrain shortest paths are quite ... geophysical.

Answer 4

First of all thank you all for your answers and contributions. Starting from your ideas, terminology, and references, I found in literature what I was searching for and with this post I would like to share it with you.

The crucial points are: (1) we can map my original problem into a well-known one known as bottleneck path (BP) problem and (2) we can solve BP in $O(|E|)$ time and its all-pairs variant (APBP) in $O(|V|^2)$ time. I will know walk you through this two points, for notation and definitions, please have a look at my first post.

1) Given every edge $(x,y) \in E$ we attach to it a weight $w(e) := -\max\{ H(x), H(y)\}$ and consider the edge-weighted undirected graph $(V,E,w)$. For a given finite path $\omega$ denote by $c(\omega)$ its bottleneck weight or capacity, defined as $\min_{e \in \omega} w(e)$. Define $c(v,w) := \max_{\omega: v \to w} c(\omega)$. It is clear that $$\Phi(v,w) = c(v,w).$$

The quantity $c(v,w)$ is called in the graph-theory literature maximum bottleneck weight or maximum capacity of a path from $v$ to $w$ and it is usually indicated as $c(v,w)$.

The problem of finding the quantity $c(v,w)$ for given $v,w \in V$ is known as bottleneck path (BP) problem and its variant when we aim to find it for all ordered pairs $v,w$ is usually called All-Pairs Bottleneck Paths (APBP) problem.

2) In his 1991 paper A. P. Punnen gives a recursive procedure (which exploits the idea described by Robert Israel) that solves the BP problem in $O(|E|)$ time.

Given a tree $T$ on $(V,E,w)$, we define its capacity as $c(T):=\min_{e \in T} w(e)$. Then one can prove that:

• If $T$ is a spanning tree of maximum capacity, then it is also a maximum spanning tree, i.e. a spanning tree of maximum weight $w(T)=\sum_{e \in T} w(e)$.
• If $T$ is a maximum spanning tree, then $c(v,w) = c_T(v,w)$, i.e. the maximum capacity between any two vertices $v,w \in V$ computed on the original graph $G$ is the same as the one computed on the subgraph $T$, which we called $c_T(v,w)$.

Therefore to solve the APBP problem, it is enough to find a maximum spanning tree, which can be done in $O(|V|^2)$ time using Prim's or Kruskal's algorithms. However we can do better: in 1978 P. M. Camerini published a paper where he proved that the min-max spanning tree problem can be solved in $O(|E|)$ time. The min-max spanning tree problem and the maximum capacity spanning tree problem are equivalent, modulo changing the sign of the weights.

Once one has a maximum (or maximum capacity) spanning tree, all the capacities $c_T(v,w)$ for all pairs $v,w \in V$ can be easily computed in $O(|V|^2)$ by running a breadth-first search algorithm on $T$, as suggested in [3].

References

[1] Camerini, P. M. (1978). The min-max spanning tree problem and some extensions. Information Processing Letters, 7(1), 1014. doi:10.1016/0020-0190(78)90030-3

[2] Punnen, A. P. (1991). A linear time algorithm for the maximum capacity path problem. European Journal of Operational Research, 53(3), 402404. doi:10.1016/0377-2217(91)90073-5

[3] Shapira, A., Yuster, R., and Zwick, U. (2009). All-Pairs Bottleneck Paths in Vertex Weighted Graphs. Algorithmica, 59(4), 621633. doi:10.1007/s00453-009-9328-x