An important computer calculation in military planning is determining the optimal paths that a set of flying objects (airplanes, cruise missiles, UAVs) should take toward their targets. The current practice is to represent the problem with static graphs, then apply search algorithms (e.g. network flow) that can yield least cost paths. A number of significant problems must be solved in order to determine optimal and realistic paths. These include the difficulty associated with representing dynamic (time dependent) and realistic phenomena, and the associated difficulties of solving the graphs with polynomial-time algorithms. In this paper we discuss the limitations of modeling with graph theoretic techniques, and we present some results that permit significantly more accurate problem representation and solution than the previous state of the art. These include: a new method for graph representation of dynamic of phenomena associated with strike routing; some general relations that are important in modeling with graphs whose edge traversals represent independent probabilistic events; and a number of new models for use in optimizations. Some of the issues and solutions that we present are very general and they are also given detailed discussion in the context of two important military problems: general radar detection representation for optimization, and representation of the overflight problem (the increased threat to strike assets as they repeat flights over threats). Finally, the models and algorithms are considered in relation to single asset routing and joint routing of multiple assets.