Developing.ru

Привет.
Дан ориентированный граф. С помощью какого алгоритма можно найти все пути между двумя узлами?

Граф состоит из N узлов. Создается матрица NxN, пусть называется А. Элемент A[i,j] устанавливается в 0, если из i-го элемента нет прямого пути в j-й, и в 1 (либо в другое положительное число, если в задаче используются веса ребер), если путь от i к j есть. Далее цепочка строится от конца: сначала вершина конца, потом все вершины, от которых есть прямой путь к вершине конца, потом все вершины, от которых есть прямые пути к тем вершинам, и т.д. В программе нужно следить за двумя вещами: чтобы не было лишних дублирующихся ветвей, и чтобы программа не зависала, если в графе будет цикл (т.е. из какой-то вершины существует путь до самой себя)

Хыиуду писал(а):Граф состоит из N узлов. Создается матрица NxN, пусть называется А. Элемент A[i,j] устанавливается в 0, если из i-го элемента нет прямого пути в j-й, и в 1 (либо в другое положительное число, если в задаче используются веса ребер), если путь от i к j есть. Далее цепочка строится от конца: сначала вершина конца, потом все вершины, от которых есть прямой путь к вершине конца, потом все вершины, от которых есть прямые пути к тем вершинам, и т.д. В программе нужно следить за двумя вещами: чтобы не было лишних дублирующихся ветвей, и чтобы программа не зависала, если в графе будет цикл (т.е. из какой-то вершины существует путь до самой себя)

Похоже на полный перебор, а точнее на поиск в глубину.
Спасибо.