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

Я так понимаю, это NP-полная задача - здесь поможет только перебор.

Мне все это видится опять же через рекурсию. Т.к. мы пишем рекурсию, то вообразим себя уже где-то посередине процесса построения одного из путей, не задумываясь (пока не задумываясь) о начале и конце...
Итак, граф задан матрицей смежности. Мы находимся в вершине Аi, позади у нас есть какой-то путь (Aa - Ab - ... - Ah - Ai -).

Мы находимся в вершине Аi, позади у нас есть какой-то путь (Aa - Ab - ... - Ah - Ai -).
Смотрим на строку вершины Ai, ищем в ней "1".
    Нашли "1" на позиции [i,j]:
        помечаем ребро [i,j] как использованное (например, присваиваем этому элементу "-1")
        добавляем в наш (текущий) путь Аj: Aa - Ab - ... - Ah - Ai - Aj
        переходим к вершине Aj, смотрим на ее строку, ищем в ней "1", ...
    Не нашли "1" нигде среди [i ][]: // т.е. пришли в конец текущего пути
        сравниваем длину текущего пути с максимальной
        удаляем из пути вершину Ai: Aa - Ab - ... - Ah
        помечаем ребро [h,i] как неиспользованное ( [h][ i] = 1 )
        смотрим на строку вершины Ah, ищем в [h][>i] "1" (начинаем с [h][i+1], т.к. в Ai мы уже пробовали ходить), ...
        

Теперь самое нелюбимое: условия выхода и начала :( .

Максимальный путь, естественно, равен нулю.
Мы хотим начать с нашей конкретно заданной вершины А0. Мы насильно записываем в начало пути А0. Ищем в А0 "1", ... .
Рано или поздно мы придем к тому, что не найдем в А0 "1" и захотим удалить А0 из пути, поднявшись на уровень вверх. По сути это будет попытка "удалить из пути вершину Аi при ( (i=0) и (длина текущего пути = 0) ) " и это будет значить, что мы уже рассмотрели все возможные пути, начинающиеся в А0, и переменная максимального пути уже содержит то, что нужно (короче пора делать return   ).
Причем условие про равенство длины текущего пути нулю обязательно и критически важно: если его опустить, то после пути типа (А0 - Аa - Ab - ... - Am - A0) мы не найдем пути (А0 - Аa-Ab-  ... - Am - Ay), y>0. Мы просто не рассмотрим их, забудем, выбросим на помойку истории...


Правильно? Я упустила что-нибудь?
Посоветуйте, пожалуйста.

Путь называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются.

Поэтому при решении задачи может получиться бесконечный путь.
Может есть правильная постановка задачи?

Это сообщение отредактировал(а) nworm - 22.5.2009, 07:46

Если выражаться этими терминами, то мы должны найти простой путь максимальной длины.

Именно для того, чтобы путь не получился бесконечным, мы и вводим дополнительное условие (которое ты назвал "простым путем"):

Ребер же все равно конечное число... И если на каждом шаге хотя бы одно мы будем блокировать, то рано или поздно доступные ребра кончатся и путь обретет свой конец. Разве нет  ?

Ну, да, так примерно, поиском в глубину путь строится.