Подскажите алгоритм

[shukshin]

Задан неориентированный граф $G (V, E)$, две вершины s, t и целое положительное
число L ($L < V ^2$). Найти существует ли в данном графе простой путь (путь в котором нет повторяющихся
ребер) от s к t длина которого (количество ребер в пути) больше или равна L, найти сам путь.
Долго думал над алгоритмом, но ничего не нашел. Проблему усугубляет еще то, что очень нежелательно использовать рекурсию, то есть обойтись АДТ, вроде стека.

[Kenelm]

Так, интуитивно кажется, что за основу можно взять алгоритм на основе динам. программирования (например, Дейкстры), только при слиянии путей в узле оставлять не кратчайший, а, наоборот, наиболее длинный. Таким образом, по окончании работы алгоритма будет выписан наиболее длинный путь от s к t.

[shukshin]

Увы, вершины в моем пути могут повторяться.
Такое впечатление, что задача решается перебором с возвратом. Однако при реализации сталкиваюсь с трудностями, например - условие возврата (ведь в графе может и не найтись нужного пути), а еще не очень понятно, как выбирать другой путь, если мы наткнулись на неверный и отошли на шаг назад, что бы алгоритм не зацикливался.

[Kenelm]

Можно тогда попробовать следующий фокус - заменить каждый узел кликой. Размер клики - равен степени узла. Каждый из узлов клики инцидентен одному из ребер исходного узла. Веса ребер внутри клики равны нулю.
Т.е. любой из узлов клики будет "представлять" исходный узел. После чего можно пробовать Дейкстру. :)

[sup]

Можно помышковать с т. Эйлера. Соединим вершины $s,t$ фиктивным ребром, а затем, "не отрывая карандаш от бумаги", обойдем весь этот граф, начиная с фиктивного ребра. Точнее, весь, может и не удастся (ну там степени вершин нечетные, то да се), но максимальный цикл гарантируется. Затем это ребро выкидываем - и вот он путь. Может что и получится ... Уж как минимум оценка сверху точно есть.

[shukshin]

тяжело алгоритм пошел, к сожалению, вот моя попытка backtracking

Используется синтаксис C++

int is_checked(Queue *G, Queue *Checked_ways, int V1, int V2)
{
        Node *q;

        for(q = Checked_ways[V1].exclude; q != NULL; q = q->next)
            if(q->vnum == V2)
                    return 1;

        for(q = Checked_ways[V2].exclude; q != NULL; q = q->next)
            if(q->vnum == V1)
                    return 1;

        return 0;
}

void search( int v, int w, int K, Queue *G, int n, Stack *s) //v ---> w (length > k), ret in Stack
{
        Queue *Checked_ways = (Queue *)calloc(n, sizeof(Queue));
        int L, tmp, flag, i, j, *prev = (int *)malloc(n * sizeof(int));
        Node *p, *q;

        for(i = 0; i < n; ++i) 
                prev[i] = -1;

        s->head = NULL; 
            
    for(tmp = v, L = 0, push(v, s); (tmp != w) || (L < K); )//пока не прийдем в вершину с нужным путем
   {
                for(flag = 0, p = G[tmp].exclude; p != NULL; p = p->next)//смотрим список смежности
                  if( !is_checked(G, Checked_ways, tmp, p->vnum) )//если в вершину можно пойти
                  {
                          flag = 1;

                          ++L;

                          prev[p->vnum] = tmp;
                          tmp       = p->vnum;

                          enq(prev[tmp], &Checked_ways[tmp]);//блокируем ребро
                          enq(tmp, &Checked_ways[prev[tmp]]);

                          push(p->vnum, s);//добавляем в путь
                          break;
                  }

                if(!flag)
                {               
                        del_queue(&Checked_ways[tmp]);//освобождаем тупиковую вершину от запретов  
           
                        enq(tmp, &Checked_ways[prev[tmp]]);
                        enq(prev[tmp], &Checked_ways[tmp]);

                          --L;
                        if(pop(s) == v && L == 0)
                        {
                                printf("No way :C");
                                del_stack(s);
                                return;
                        }
                        tmp = prev[tmp];
                }
        }

    return;
}

Граф храню в массиве очередей, дублируя ребра. Для каждой вершины храню те, в которых мы уже были. Все равно не то.
(Например могут затираться prev при долгом пути).Условие выхода - тащим из стека исходную с 0-вым путем при отходе назад. Сложно сформулировать алгоритм, мне все-таки нужна ваша помощь.
Прошу подкорректировать мою идею хотя бы.

[Kenelm]

shukshin
Кстати, тут погуглил немного на эту задачу - действительно она NP-трудная и всякими "дейкстроподобными" алгоритмами не совладать.Однако народ работает.

[Skeptic]

Строится матрица смежности графа с нулевой диагональю. При возведении матрицы в степень $n$ строка $i$ содержит количество всех путей длиной $n$ из вершины $i$ ко всем вершинам графа. Анализ содержания строки $i$ в обратном расчёту порядке позволит найти конкретные пути.

[provincialka]

Пути получатся не обязательно простые