Посмотри книжки по теории графов, особенно кратчайший путь (алгоритм Дейкстры) и кратчайшие n путей. Это не коммивояжер, они оба полиномиальные (n^2, n^3) и довольно простые в программировании. Хотя коммивояжер тоже простой в реализации. Если все-таки получится NP задача, то смотри приближенные методы решения задач комбинаторной оптимизации, они могут получиться гораздо проще, т.е. реально решаемыми. Но мне кажется все сведется к Дейкстре. Ссылок на источники в сети у меня нет.