- Автор темы
- #1
Добрый день, столкнулся с такой проблемой нужна реализация поиска из серии "друзья друзей" для социалки с возможностью вычисления кратчайшего маршрута между двумя произвольно заданными точками.
Т.е. имеем дерево с вершиной в точке А и подчиненными точками B,C,D и т.п. каждая из точек может являться вершиной для других деревьев с подчиненными точками ВA,BB,BC,CA,CB,CC. В свою очередь каждая из этих вершин имеет свои подчиненные точки. Деревья могут образовывать петли, например точка СА и начальная точка могут быть одинаковыми.
В результате работы алгоритма нужно находить:
1. кратчайший маршрут между заданными точками
2. список всех точек на расстоянии с заданным количеством хопов
3. ближайшая петля для заданного количеством хопов
Все это практически в чистом виде работа протокола OSPF который и работает на алгоритме Дейкстры.
Интересно было бы увидеть примеры реализации на PHP или любом другом языке программирования.
Вот нашел еще интересный вариант:
Также интересно было бы узнать наиболее оптимальный алгоритм для решения этой задачи, если максимальное количество подчиненных точек в каждом дереве от 10 до 100
Т.е. имеем дерево с вершиной в точке А и подчиненными точками B,C,D и т.п. каждая из точек может являться вершиной для других деревьев с подчиненными точками ВA,BB,BC,CA,CB,CC. В свою очередь каждая из этих вершин имеет свои подчиненные точки. Деревья могут образовывать петли, например точка СА и начальная точка могут быть одинаковыми.
В результате работы алгоритма нужно находить:
1. кратчайший маршрут между заданными точками
2. список всех точек на расстоянии с заданным количеством хопов
3. ближайшая петля для заданного количеством хопов
Все это практически в чистом виде работа протокола OSPF который и работает на алгоритме Дейкстры.
Интересно было бы увидеть примеры реализации на PHP или любом другом языке программирования.
Вот нашел еще интересный вариант:
Для просмотра скрытого содержимого вы должны войти или зарегистрироваться.
Также интересно было бы узнать наиболее оптимальный алгоритм для решения этой задачи, если максимальное количество подчиненных точек в каждом дереве от 10 до 100