"Relatives" of the shortest path problem

Question

Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such that some function of the edge weights on the path is minimum. In this sense they are all "relatives" of the shortest path problem; in the latter the function is simply the sum.

Note: We are looking for simple paths, that is, without any repeated vertices. Since I did not find standard names for these problems in the literature, I named them myself.

Path with minimum weight gap: find an $s-t$ path, such that the difference between the largest and smallest edge weights on the path is minimum.

Smoothest path: find an $s-t$ path, such that the largest step size on the path is minimum, where a step size is the absolute value of the weight difference between two consecutive edges.

Path with minimum altitude: Let us define the altitude of a path by the sum of the step sizes along the path (see the definition of step size above). Find an $s-t$ path with minimum altitude.

Path with minimum prime weight: assuming that all edge weights are positive integers, find an $s-t$ path, such that its weight is a prime number. If there is such a path, find one with the smallest possible prime weight.

Question: what is known about these path problems? (And others that could be conceived in a similar spirit, applying a different function of the weights.) In general, is there any guidance that which functions of the edge weights can be minimized in polynomial time, and which are NP-hard?

Note: it is interesting, for example, that while the sum of the weights is easy to minimize (it is the classical shortest path problem), but minimizing the closely related average of the weights on the path is NP-hard. (Assign weight 2 to all edges incident to $s$ and $t$, and weight 1 to all others. Then a min average weight path will be a longest $s-t$ path).

Answer 1

Here is an answer to the first problem:

Path with minimum weight gap: find an $s-t$ path, such that the difference between the largest and smallest edge weights on the path is minimum.

A paper from 1984 shows that whenever we can decide feasibility (does there exist a solution in the unweighted case) for some combinatorial optimization problem in polynomial time, then we can also find in polynomial time a solution that minimizes the differenc between the largest and smallest cost coefficient (in the weighted case):

S. Martello, W.R. Pulleyblank, P. Toth, D. de Werra
Balanced optimization problems
Operations Research Letters 3, 1984, Pages 275-278

This implies a polynomial time algorithm to your question.

Answer 2

Path with minimum weight gap: This can be solved in time $\tilde{O}(|E|^2)$, where $|E|$ is the number of edges (assuming $|E|$ is at least linear in the number of vertices). You can loop over the minimum weight, and do binary search (or efficient updates) over the maximum weight, and check connectivity. I do not know whether this can be improved.

Path with minimum altitude (in your terminology): This can be solved in time $\tilde{O}(|E|)$. You can compute distance (as in sum of 'step' sizes) to all edges analogously to ordinary weighted shortest path. Note that repeated vertices cannot shorten a path. To efficiently handle high degree vertices (as in avoiding time $|E|^2$), you can split a vertex of degree $k$ into a path of $k-1$ vertices.

Path with minimum prime weight: If the weights are in binary, this should be NP complete: Use weight 1 edges, except for the initial high-weight edge such that only a Hamilton path has prime weight (weight is the sum of edge weights). (A caveat is that we have not proved that large-enough primes (even without minimum prime gaps) can be quickly found without randomness.) Even for unary weights, I do not expect it to be in P.
Minimum prime weight allowing self-intersections: In P for unary weights. If, in place of the set of primes, we used a set of random numbers $S$ with density $Θ(n/\log n)$, then with probability 1, it is in $\mathrm{P}^S$ even for binary weights: It suffices to keep track of polynomially many (dependent on $S$) lowest path weights at each point. However, with prime weights, we may have to diversify divisors of weight differences (instead of just keeping track of lowest weights), and it is unclear whether that is enough.

Smoothest path: NP complete. If we allowed self-intersections, this would be solvable in time $\tilde{O}(|E|)$, but for the version without self-intersections, here is a reduction from 3-SAT with $n$ variables. Have vertices $s=v_0,v_1,...,t=v_n$, plus a vertex for each clause. For each variable $x_i$ ($i<n$), add a smooth path (using extra vertices if necessary) from $v_i$ to $v_{i+1}$ that passes through all clauses with positive occurrence of $x_i$, and a similar path for clauses with $¬x_i$. Set the first and last edge weight of each path to 1 (or another constant), but otherwise choose weights such that no other paths are smooth. Finally, duplicate all clause vertices and the adjoining edges; this way each clause can be visited at most twice, which suffices for 3-SAT.