Is there a clever (meaning fast) way to compute this?
Not so much.
Because there is no limitation on what a move will "cost", pruning the choice tree early isn't helpful. Also, there's no way to prioritise choices at an intermediate stage.
All paths have to be checked.
If this was a TSP (find the minimum path length) problem, with only non-zero edges, and you had a "best min so far", you could limit choices that immediately exceed that "best min so far". But you have negative-valued edges. And if you had a "best max so far", it's not clear how to avoid traversing the whole tree.
-QM
--
Quantum Mechanics: The dreams stuff is made of