Изменения

Если же граф симметрический (т.е. для всех пар вершин (i, j) длины дуг в обоих направлениях одинаковы ), то каждая поездка в обоих направлениях имеет одну и ту же длину/стоимость. Симметрия делит пополам количество возможных поездок.

Можно предположить, что для решения задачи необходимо просто сгенерировать все n! всевозможных перестановок вершин полного графа,подсчитать для перестановки длину маршрута и выбрать минимальный. Но тогда задача оказывается неосуществимой для достаточно небольших n.

Так же известно, что задача о коммивояжере относится к NP-полным задачам.