Прохождение Графа

[hclubmk]

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

[patzer2097]

Попробуйте поискать так

[hclubmk]

patzer2097
это не Гамильтонов контур (я его решаю), задача сложнее - читайте постановку внимательнее.

hclubmk писал(а):

(вершины разные)

[patzer2097]

а я Вам предлагаю почитать про гамильтонов путь, а не цикл

[ИСН]

Сдаётся мне, речь шла про граф, где Гамильтонова пути может и не быть
Кратчайший путь, однако, какой-то по-любому есть.

[patzer2097]

ИСН в сообщении #896758 писал(а):

Сдаётся мне, речь шла про граф, где Гамильтонова пути может и не быть

если гамильтонова пути в графе $G$ нет, мы всегда можем рассмотреть взвешенный граф $G'$, ребро которого между $i$ и $j$ имеет вес $\rho_G(i,j)$, где $\rho_G$ - метрика, заданная графом $G$. Эти веса считаются быстро, и сформулированная задача для графа $G$ равносильна задаче о кратчайшем гамильтоновом пути в $G'$

[hclubmk]

Хотелось бы получить конкретную ссылку на конкретный алгоритм. Например: решение задачи коммивояжера методом Литтла.
Если таковыx не имеется, просьба не кидать [censored] на вентилятор разводить демагогию.

[Deggial]

hclubmk в сообщении #896810 писал(а):

[censored]

hclubmk, предупреждение за обсценную лексику.

[ИСН]

Веса-то быстро, но как найти кратчайший гамильтонов путь во взвешенном графе, если даже найти хоть какой-нибудь из них в простом графе - задача NP-полная?

[patzer2097]

ИСН в сообщении #896821 писал(а):

но как найти кратчайший гамильтонов путь во взвешенном графе, если даже найти хоть какой-нибудь из них в простом графе - задача NP-полная

ну это известная задача, она называется "задача коммивояжера", очень популярный объект исследования сейчас. Для нее построено множество разных алгоритмов, например, тут масса примеров с открытым кодом. Правда, в стандартной в этой задаче рассматриваются гамильтоновы циклы - т.е., простые циклы, проходящие через все вершины; если мы хотим рассматривать путь с началом $u$ и концом $v$, проходящий по разу через все вершины, то можно добавить в граф новую вершину $\varepsilon$, соединенную с $u$ и $v$ ребрами веса $0$ и не соединенную ни с какими другими

[ИСН]

А, чёрт, ну да, это же она и есть, не узнал. То есть тоже полнопереборная, но придуманы какие-то эвристики, обычно работающие хорошо.

[patzer2097]

ИСН в сообщении #896836 писал(а):

То есть тоже полнопереборная, но придуманы какие-то эвристики, обычно работающие хорошо.

Не совсем переборная, есть стандартные точные алгоритмы, работающие за $O\left(2^{n+o(n)}\right)$, а перебор требует порядка $n!$ операций

[hclubmk]

patzer2097 в сообщении #896834 писал(а):

можно добавить в граф новую вершину $\varepsilon$, соединенную с $u$ и $v$ ребрами веса $0$ и не соединенную ни с какими другими

Работает, спасибо.

[hclubmk]

А не логичнее не добавлять вершину, а просто запретить все переходы в $u$ и из $v$?