поиск кратчайшего пути проходящий через ВСЕ города C++

[vo_sa]

Имеется n городов. Некоторые из них соединины дорогами известной длины. Вся система дорог задана квадратной матрицей порядка n, элемент a(ij)который равен некоторому трицательному числу, если город i не соединен напрямую дорогой с городом j и равено длине дороги, впротивном случае (i,j = 1,..., n). В предположении, что каждый город соединен напрямую с дорогой с каждым, найти кратчайший маршрут начинающийся в 1-ом городе и проходящий через все остальные. С++


такое решается?? в инете МНОГО всего нашёл, когда кратчайший путь путь из однго в другой, а через все нету
алгоритм хотябы предложите какойнить

[MaTBeu]

Обход графа в глубину:
Алгоритм:
У вас есть два стека:
Стек пройденных вершин и стек смежных вершин.
1. Заносите начальную точку в стек пройденных вершин.
2. Заносите в стек смежных вершин, все смежные вершины
3. Проверяете последнюю из занесенных смежных вершин на "проверенность", если она еще не проверена, то заносим ее в стек пройденных вершин, и начинаем алгоритм с этой вершины.

Алгоритм заканчивается, когда будут пройдены все вершины графа.

Обход графа в ширину:
Список пройденных вершин и очередь смежных вершин.
1. Заносим первую вершину в список провернных вершин.
2. В очередь заносим все смежные вершины
3. Проверяем каждую смежную вершину в очереди на "проверенность"
4. Заносим в список пройденных все смежные вершины
5. Последняя в очереди смежная вершина - становится начальной
6. Цикл повторяется до тех пор, пока все вершины не будут пройдены

А про кратчайший путь - Алгоритм Дейкстры.

[vo_sa]

тут смежнные вершины не причём. каждый кород СВЯЗАН с каждым!!!