  By a new type of finite size scaling analysis on the square lattice, and by
renormalization group calculations on hierarchical lattices we investigate the
effects of dilution on optimal undirected self-avoiding paths in a random
environment. The behaviour of the optimal paths remains the same as for
directed paths in undiluted medium, as long as forbidden bonds are not
exceeding the percolation threshold. Thus, overhanging configurations do not
alter the standard self-affine directed polymer scaling regime, even above the
directed threshold, when they become unavoidable. When dilution reaches the
undirected threshold, the optimal path becomes fractal, with fractal dimension
equal to $D_{\rm min}$, the dimension of the minimal length path on percolation
cluster backbone. In this regime the optimal path energy fluctuation,
$\overline{\Delta E}$, can be ascribed entirely to minimal length fluctuations,
and satisfies $\overline{\Delta E} \propto L^{\omega}$, with $\omega=1.02 \pm
0.06$ in $2d$, $L$ being the Euclidean distance. Hierarchical lattice
calculations confirm that $\omega$ is also the exponent of the leading scaling
correction to $\overline E \propto L^{D_{\rm min}}$.
  Upon approaching threshold, the probability, ${\cal R}$, that the optimal
path does not stick entirely on the minimal length one, obeys ${\cal R} \sim
\left( \Delta p\right) ^{\rho}$, with $\rho \sim 1.0 \pm 0.05$ on hierarchical
lattices. Such behaviour could be characteristic of the crossover to fractal
regime. Transfer matrix results on square lattice show that a similar full
sticking does not occur for directed paths at the directed percolation
threshold.
