It seems to me this is a combined minimum spanning tree and shortest path problem. First compute the MST in the temperature graph to find the path with the lowest max temperature. Then build the subgraph containing only those distances corresponding to edges that have a temperature no larger than the max temperature found by the MST algorithm. Finally, run a shortest path algo on the subgraph.
How is it a double shortest paths problem? Maybe you just view what I think of as an MST as a shortest path?
--Rrenaud 13:44, 14 Mar 2005 (EST)