In several scenarios in which new robots and tasks are added to a network of already deployed, interchangeable robots, a trade-off arises in seeking to minimize cost to execute the tasks and the level of disruption to the system, This paper considers a navigation-oriented variant of this problem and proposes a parameterizable method to adjust the optimization criterion: from minimizing global travel time (or energy, or distance), to minimizing interruption (i.e., obtaining the fewest number of robot reassignments), and mixtures in-between. Paths are computed by task-allocation formulation in which destination locations of newly deployed robots are added as tasks to an existing allocation. We adapt the graph matching variant of the Hungarian algorithm—originally designed to solve the optimal assignment problem in complete graphs—to construct routing paths by showing that there is a three-dimensional spatial interpretation of the Hungarian bipartite graph. When new agent-task pairs are inserted, the assignment is globally reallocated in an incremental fashion so it requires only linear time when the robots’ traversal options have bounded degree. The algorithm is studied systematically in simulation and also validated with physical robots.