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