El problema requiere buscar entre dos nodos determinados ~a~ y ~b~ el camino mínimo donde el costo del camino es la máxima arista del mismo. Para resolver este problema es necesario precalcular todas las distancias entre todos los nodos para responder cada pregunta en ~O(1)~. Se puede usar para esto ~n~ veces el algoritmo de Dijkstra o usar el algoritmo de Floyd-Warshall.

Complejidad: ~O(n^3)~ si se usa Floyd-Warshall o ~O(n^2 + (n \cdot m) \cdot \log m))~ usando Dijkstra.