This Demonstration addresses the approach proposed in [1] to compute the stability radius of an optimal solution to the shortest path problem. The stability radius is the largest non-negative that satisfies the inequality:

The right-hand side is a linear function in the variable . The left-hand side is the value function of a parametric version of the initial shortest path problem, where the objective coefficients are linear functions of . Call this the value function . It is well-known that is a continuous, piecewise-linear, and concave function of . The detailed steps to construct function can be found in [1].

The algorithm is tested for two graph types. The "LayerGraph" is generated by several so-called vertex layers. The vertices on the same layer are not connected and each vertex on any layer is adjacent to all vertices from adjacent layer(s). In the "NormalGraph", the edges are generated with equal probability for all pairs of vertices. Both graphs are connected and have at least one path between given source and destination. Note that edge weights correspond to edge colors.