Алгоритм поиска кратчайшего пути при обходе всех вершин графа

Подскажите, пожалуйста, алгоритм (название), который(-ые) могут использоваться для ПОИСКА минимального пути при обходе ВСЕХ вершин графа.
Или алгоритм для поиска гамильтонового пти (но не цикла) - задача коммивояжера.

Примечание:
Граф, оно же дерево - это совокупность вершин (листьев) и ребер (дуг), связывающих вершины. Каждая дуга имеет свой удельный вес.

Примечание:
Давайте сразу уточню.
Задача стоит такая: необходимо из ПЕРВОЙ вершины обойти ВСЕ вершины минимальным путем.
Дейкстра здесь не подходит.

Примечание:
В данном случае задача коммивояжера не является метрической.

Ответы:

Без имени

А че бы самому не соствавить? (я не знаю, что такое "граф").

Agni

Гляньте это: [1], [2].

Без имени

Есть 2 способа цикл замутить. Причем 2-й только время сокращает (со счетчиком). У вас вопрос про составление алгоритма. Если внятно вопрос сформулируете, я вам алгоритм составлю

warrior

может быть вы имеете в виду алгоритм Дейкстры?

malek

"Граф, оно же дерево" - бред. Дерево - это частный случай, когда циклов нет.

malek

"совокупность вершин (листьев)" - листьями принято называть вершины степени 1

Agni

Интересно, какой идиотик проминусовал конкретные ответы людей, которые хотели помочь человек?

Agni

Кроме Дейкстры по ссылкам есть ещё алгоритмы, ни один не подходит?

malek

Вот здесь есть 3/2-приближённый алгоритм для задачи о коммивояжере (то есть выдающий ответ, который не более чем в полтора раза хуже оптимального). Зато он полиномиальный.

objMihail

Может использоваться генетический алгоритм.

Mirraz7

А вообще задача NP-полная => единственный алгоритм поиска точно оптимального решения - перебор.

16 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.