Networkx предоставляет примерное решение для TSP, см. page . Их решение основано на записи TSP как задачи Quadrati c Unconstrained Binary Optimization (QUBO).
Обратите внимание, что доказано, что нахождение альфа-приближения к TSP в целом оказывается NP-сложным. Таким образом, вы не можете гарантировать качество полученного результата. Как бы то ни было, есть частный случай, Евклидово-TSP, где мы можем построить 2-аппроксимацию и даже 1,5-аппроксимацию TSP, используя алгоритм Christofides , однако я не смог найти реализацию этого алгоритма в Networkx.