| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Delphi]Нахождение всех путей из i-й в j-ю точку |
| Автор: tores 29.3.2008, 20:24 |
| Здравствуйте. Столкнулся с такой задачкой на практике по ЭВМ. Дан не взвешенный неориентированный граф A с n вершинами. Если i-я вершина соединена с j-й то элемент a[i,j]=1, иначе a[i,j]=0. Найти все пути из i-ой вершины в j-ую ( без петель ). Алгоритмы нахождения кратчайшего пути находил, а вот для такой задачи не могу найти. Программер я зеленый -(, поэтому обращаюсь к вам. Как реализвовать этот алгоритм? И нет ли алгоритма на Delphi? |
| Автор: kBepTu 29.3.2008, 22:29 |
| Задача по теме дискретная математика, на графы не точно: нужно возвести матрицу смежности А в n степень чтобы найти количество маршрутов между вершинами (эл-т a[i,j]) ЗЫ: гугли (матрица А - в твоем случае матрица смежности) ЗЗЫ: n - длина маршрута, т.е. X->Y->Q->P - длина 3 ,т.е нужно возмести матрицу в 3 степень |
| Автор: comtat 30.3.2008, 15:32 |
| вот http://www.algolist.ncstu.ru/maths/graphs/ должно помочь |
| Автор: tores 30.3.2008, 23:42 |
| Всем спасибо, я еще поразбираюсь. Если что я зайду -) |