A method for optimizing the vertical profile to be flown by an aircraft during a cruise phase of a flight, comprising: (a) determining all potentially relevant step locations along potential cruise flight paths of the aircraft between defined or selected start and end points, wherein step locations are locations at which an altitude change is assessed, and wherein said determining comprises: calculating cost curves for segments of the potential cruise flight paths at all legally available flight levels in parallel, the cost curve of each segment based on an aircraft performance model, wherein calculating cost curves includes calculating the estimated fuel consumption for each segment; and determining all intersections between the cost curves and identifying the intersections as potential step locations; (b) generating digital data representing a weighted graph, the weighted graph based on the cost of all level segments and step segments along the potential cruise flight paths, wherein the weighted graph comprises a mesh of nodes connected by edges, wherein each node represents an intersection between cost curves and wherein each edge is weighted by the cost of all level segments or all step segments, respectively, between the nodes connected by said edge, wherein the cost comprises fuel cost and time cost set into relation by a cost index; (c) solving a cruise optimization problem by applying graph theory to the weighted graph, wherein said solving comprises using a path finding algorithm to find lateral and vertical edges in the weighted graph which represent an optimal vertical profile; (d) outputting step locations and altitudes of an optimized vertical profile resulting from solving the cruise optimization problem; (e) generating a predicted trajectory along a route based on the step locations and altitudes of the optimized vertical profile; and (f) displaying at least a portion of the optimized vertical profile corresponding to a portion of the route on a cockpit graphical display system. (a) determining all potentially relevant step locations along potential cruise flight paths of the aircraft between defined or selected start and end points, wherein step locations are locations at which an altitude change is assessed, and wherein said determining comprises: calculating cost curves for segments of the potential cruise flight paths at all legally available flight levels in parallel, the cost curve of each segment based on an aircraft performance model, wherein calculating cost curves includes calculating the estimated fuel consumption for each segment; and determining all intersections between the cost curves and identifying the intersections as potential step locations; calculating cost curves for segments of the potential cruise flight paths at all legally available flight levels in parallel, the cost curve of each segment based on an aircraft performance model, wherein calculating cost curves includes calculating the estimated fuel consumption for each segment; and determining all intersections between the cost curves and identifying the intersections as potential step locations; (b) generating digital data representing a weighted graph, the weighted graph based on the cost of all level segments and step segments along the potential cruise flight paths, wherein the weighted graph comprises a mesh of nodes connected by edges, wherein each node represents an intersection between cost curves and wherein each edge is weighted by the cost of all level segments or all step segments, respectively, between the nodes connected by said edge, wherein the cost comprises fuel cost and time cost set into relation by a cost index; (c) solving a cruise optimization problem by applying graph theory to the weighted graph, wherein said solving comprises using a path finding algorithm to find lateral and vertical edges in the weighted graph which represent an optimal vertical profile; (d) outputting step locations and altitudes of an optimized vertical profile resulting from solving the cruise optimization problem; (e) generating a predicted trajectory along a route based on the step locations and altitudes of the optimized vertical profile; and (f) displaying at least a portion of the optimized vertical profile corresponding to a portion of the route on a cockpit graphical display system.