Las aeronaves requieren una gran cantidad de combustible para generar suficiente potencia para realizar un vuelo. Ese consumo provoca la emisión de partículas contaminantes como el dióxido de carbono, que está implicado en el calentamiento global. Este documento propone un algoritmo que puede proporcionar la trayectoria de referencia en 3D que minimiza los costos de vuelo y el consumo de combustible. El algoritmo propuesto fue concebido utilizando la metodología de Floyd-Warshall como referencia. Se tuvo en cuenta el clima utilizando pronósticos proporcionados por Weather Canada. El espacio de búsqueda se modeló como un grafo dirigido ponderado. El consumo de combustible se calculó utilizando el modelo Base of Aircraft Data (BADA) desarrollado por Eurocontrol. Las trayectorias entregadas por el algoritmo desarrollado se compararon con los planes de vuelo de larga distancia calculados por una aerolínea europea y con trayectorias reales obtenidas de . Los resultados revelan que se puede reducir hasta 2000 kg de combustible por vuelo, y el tiempo de vuelo también se puede reducir en hasta 11 minutos.