  We consider the question of speeding up classic graph algorithms with
machine-learned predictions. In this model, algorithms are furnished with extra
advice learned from past or similar instances. Given the additional
information, we aim to improve upon the traditional worst-case run-time
guarantees. Our contributions are the following:
  (i) We give a faster algorithm for minimum-weight bipartite matching via
learned duals, improving the recent result by Dinitz, Im, Lavastida, Moseley
and Vassilvitskii (NeurIPS, 2021);
  (ii) We extend the learned dual approach to the single-source shortest path
problem (with negative edge lengths), achieving an almost linear runtime given
sufficiently accurate predictions which improves upon the classic fastest
algorithm due to Goldberg (SIAM J. Comput., 1995);
  (iii) We provide a general reduction-based framework for learning-based graph
algorithms, leading to new algorithms for degree-constrained subgraph and
minimum-cost $0$-$1$ flow, based on reductions to bipartite matching and the
shortest path problem.
  Finally, we give a set of general learnability theorems, showing that the
predictions required by our algorithms can be efficiently learned in a PAC
fashion.
