It is widely recognized that reliable communications are a key element of a successful response to a disaster situation. To address this need, local and regional governments in all parts of the world have deployed dedicated communications networks for first responders. These systems are often prohibitively expensive, voice-only, and are needed only on rare occasions. It would be more cost-effective to use already-existing networks or to deploy networks for shared use. However, due to the sudden increase in demand or physical failure caused by the disaster, shared networks may become overloaded. In such situations, it would be desirable to prioritize traffic flows belonging to public safety applications over others. Solutions such as priority queuing and differentiated services provide partial answers to that goal but leave other problems unsolved. This work presents a novel solution using Segment Routing and a Genetic Algorithm optimizer to minimize the impact of network overload on critical traffic flows. The results show that these methods can reroute flows using a single midpoint such that the total network overload is reduced compared to traditional shortest-path routing while avoiding unnecessarily long paths and taking priority of flows into account.