  Graph algorithms are widely used for decision making and knowledge discovery.
To ensure their effectiveness, it is essential that their output remains stable
even when subjected to small perturbations to the input because frequent output
changes can result in costly decisions, reduced user trust, potential security
concerns, and lack of replicability. In this study, we consider the Lipschitz
continuity of algorithms as a stability measure and initiate a systematic study
of the Lipschitz continuity of algorithms for (weighted) graph problems.
  Depending on how we embed the output solution to a metric space, we can think
of several Lipschitzness notions. We mainly consider the one that is invariant
under scaling of weights, and we provide Lipschitz continuous algorithms and
lower bounds for the minimum spanning tree problem, the shortest path problem,
and the maximum weight matching problem. In particular, our shortest path
algorithm is obtained by first designing an algorithm for unweighted graphs
that are robust against edge contractions and then applying it to the
unweighted graph constructed from the original weighted graph.
  Then, we consider another Lipschitzness notion induced by a natural mapping
that maps the output solution to its characteristic vector. It turns out that
no Lipschitz continuous algorithm exists for this Lipschitz notion, and we
instead design algorithms with bounded pointwise Lipschitz constants for the
minimum spanning tree problem and the maximum weight bipartite matching
problem. Our algorithm for the latter problem is based on an LP relaxation with
entropy regularization.
