Stochastic Shortest Path (SPP) problems are Markov Decision Processes that have many applications in discrete settings but can also be used to produce discretizations of stationary Hamilton-Jacobi-Bellman PDEs describing the cost of optimal controls in indefinite-horizon problems (where the process terminates upon reaching a prescribed target). For deterministic shortest path problems on graphs, the solution is easy to find via non-iterative label-setting algorithms such as Dijkstra’s classical method. Unfortunately, label-setting algorithms are inapplicable to general SSPs, but there are well-known non-trivial examples of SSPs for which they produce the right answer. This observation led to development of (non-iterative) Dijkstra-like methods for Eikonal PDEs describing isotropic optimal control problems. Much subsequent work has focused on extending such non-iterative techniques to more general (anisotropic) problems. We will present a broad subclass of SSPs called Opportunistically-Stochastic Shortest Path (OSSP) problems, for which the applicability of label-setting algorithms is easy to guarantee a priori. We use OSSPs in two very different applications: (1) finding a simple geometric characterization of anisotropic min-time control problems in 2D and 3D, for which label-setting methods are applicable; and (2) introducing a new stochastic model of optimal lane-switching by autonomous vehicles and showing that it can be solved by a Dijkstra-like method. Both of these are joint work with Ph.D. student Mallory Gaspard. Based on https://arxiv.org/abs/2310.14121