По университету помню, использовали для решения алгоритм Коммивояжера или Муравьиный алгоритм. Оба работают, вопрос в реализации. Учитывая, что по логике они схожи, но не идентичны, осмелюсь предположить, что вполне возможна реализация с использованием данного алгоритма. Единственное, что два предыдущих алгоритма используются для поиска наикратчайшего пути по всему графу, в этом разница. Как вариант, можно попробовать алгоритм Левита.
Вопрос, если у Вас известны ребра, то почему граф не взвешенный? Возможно я что-то не понял, заранее прошу прощения.