Нахождение всех путей из i-й в j-ю точку.

Здравствуйте.
Столкнулся с такой задачкой на практике по ЭВМ.
Дан не взвешенный неориентированный граф A с n вершинами. Если i-я вершина соединена с j-й то элемент a[i,j]=1, иначе a[i,j]=0. Найти все пути из i-ой вершины в j-ую ( без петель ).
Алгоритмы нахождения кратчайшего пути находил, а вот для такой задачи не могу найти.
Программер я зеленый -(, поэтому обращаюсь к вам.

Добавлено 29.03.08, 17:20
Как это можно представить на Delphi? Или вообще представить?

Нумеруете лексикографическим порядоком все пути длиной меньшей количества вершин

Каждый путь проверяете подходит или нет

Цитата

ОБЩАЯ СХЕМА АЛГОРИТМА С ВОЗВРАТОМ
Пусть решение, которое мы ищем, имеет вид последовательности <X(1), …, X(n)>.
Будем строить его, начиная с пустой последовательности длины 0.
Пусть на каком-то этапе уже построено частичное решение длины i: < X(1), …, X(i) >.
Попытаемся продолжить это решение еще на один шаг. Для этого нужно отыскать допустимое X(i+1). X(i+1) считается допустимым, если или < X(1), …, X(i+1) > уже является решением, или относительно < X(1), …, X(i+1) > нельзя сразу сказать, что его невозможно расширить до полного решения.
Дальше существует две возможности:
– если X(i+1) допустимо, то следующее допустимое X ищется для частичного решения <X(1), …, X(i+1)> (заметим, что допустимость X(i+1) вовсе не означает, что <X(1), …, X(i+1)> можно расширить до полного решения);
– если допустимого X(i+1) не существует, то возвращаемся на шаг назад – к частичному решению < X(1), …, X(i -1) > и для него отыскиваем другое X’[i], не совпадающее с предыдущим X(i).
Более точно, пусть для каждого i > 0 существует множество B(i), из которого будут выбираться X(i) – претенденты на i–ю координату частичного решения.
Очевидно, множества B(i) должны содержать все X(i), занимающие i-ю координату любого решения. Кроме того, B(i) всегда будут содержать какие-то лишние элементы, не содержащие в i–й координате ни одного решения.
Если предположить, что все решения имеют длину <= n, и все множества B(k) состоят из конечного числа элементов, то этот алгоритм находит все решения.
Запишем общую схему алгоритма с возвратом с помощью рекурсии.
{рекурсивный вариант алгоритма с возвратом}
1 procedure BC(k);
{генерируем все решения, являющиеся продолжением частичного решения <X[1],…,X[k-1]>, массив Х–глобальный}
2 begin
3 for y из B(k) do
4 if y допустим then
5 begin
6 X[k]:= y;
7 if <X[1],…,X[k]> – решение then
8 write(<X[1],…,X[k]>);
9 BC(k+1); {генерируем все решения, являющиеся продолжением частичного решения <X[1],…,X[k-1],y>}
10 y неиспользован;{возврат на <X[1],…,X[k-1]>}
11 end {цикл 3 выберет для продолжения<X[1],…,X[k-1]> следующий y'<>y}
12 end;


Применим теперь алгоритм с возвратом для поиска всех путей между парой фиксированных вершин s и t в графе G=<V,E>, заданном матрицей инциденций A[u,v], u,v из V. Каждый такой путь – последовательность различных вершин графа <X(1), …, X(k)>, где s=X[1], t=X[k], k – количество вершин в пути, соседние вершины X(i) и X(i+1) соединены ребром. Тогда B(i) = V (множество всех вершин) для любого i<=n.

Условие допустимости вершины y для продолжения <X(1), …, X(i-1)>:
1. A[X(i-1),y]=1 (вершина y соединена ребром с X(i-1));
2. y новая (не принадлежит <X(1), …, X(i-1)>), т.е. DOP[y]=истина.

АЛГОРИТМ {Нахождение всех путей между парой фиксированных вершин в неор. графе}
Данные: Граф G=<V,E>, представленный матрицей инциденций A[u,v], где u,v из V, пара выделенных вершин s и t.
Результаты: Печать всех путей между s и t.
Переменные A, X, DOP, s, t – глобальные.
1 procedure go(i);
{генерация всех путей между s и t, являющихся продолжением частичного решения <s=X[1],…,X[i-1]>}
2 begin
3 for y:=1 to n do
4 if (A[X[i-1],y]=1)AND(y=t) then write(X[1],…,X[i-1],y)
5 else if DOP[y] then
6 begin
7 X[i]:=y; DOP[y]:=ложь;
8 go(i+1);
{возврат}
9 DOP[y]:= истина;
10 end
11 end;

1 begin {основная программа}
2 for v:=1 to n do DOP[v]:=истина;
3 for v:=1 to n do X[v]:=0;
4 X[1]:=s; {s – начало пути}
5 DOP[s]:= ложь; {s включена в решение}
6 go(2);
7 end.

Сообщение отредактировано: Swetlana - 29.03.08, 18:48

Tores помоему алгоритмы Флойда и Дейкстры дают как промежуточный результат ... как раз длины путей если надо то могу скинуть у меня была на диске реализация на Pascal ...

Цитата andrew.virus @ 30.03.08, 18:12

Tores помоему алгоритмы Флойда и Дейкстры дают как промежуточный результат ... как раз длины путей если надо то могу скинуть у меня была на диске реализация на Pascal ...

НЕ понял, что вы предлагаете?

Длины путей:? Каких путей? Зачем они нужны?

Цитата esperanto @ 29.03.08, 17:39

Нумеруете лексикографическим порядоком все пути длиной меньшей количества вершин

длина меньшая количества вершин не гарантирует отсутствия петель.

Цитата andriano @ 30.03.08, 18:14

Цитата esperanto @ 29.03.08, 17:39

Нумеруете лексикографическим порядоком все пути длиной меньшей количества вершин

длина меньшая количества вершин не гарантирует отсутствия петель.

да. вобщем то я не утверждал этого

На случай, если кто-то не обратил внимание.
Пусть поиском в глубину ищется один произвольный путь от s до t на графе. В поиске в глубину просмотренная вершина помечается, и больше ее использовать нельзя. Если после выхода из рекурсии вершину обновлять, то линейный поиск в глубину превращается в экспонециальный алгоритм с возвратом, и один путь - во всевозможные пути от s до t.

Блин, вот я лох, многие сказаные понятия не понимаю. Я еще поищу что-нибудь.
Алгоритм Прима нашел в инете (нахождение минимального остова дерева), в нем разобрался вроде. Думал на его основе что то сделать, но не могу, не представляю. А вообще можно как то разбить на несколько процедур поиск из 1й допустим вершины во 2ю, т.е. чтобы алгоритм попробовал дойти из 1 в вершину 2 через все остальные вершины и посчитал бы их количество?

Цитата Tores @ 30.03.08, 20:49

А вообще можно как то разбить на несколько процедур поиск из 1й допустим вершины во 2ю, т.е. чтобы алгоритм попробовал дойти из 1 в вершину 2 через все остальные вершины и посчитал бы их количество?

Можно конечно.


Также можно решить используя мартингалы или трансформ фурье или полукольца или интегралы. Вопрос, зачем?


В худшем случае задача принадлежит класу PSPACE а посему полный перебор асимптотически оптимален