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