Нужно реализовать алгоритм Дейкстры

Тема в разделе "Как сделать...", создана пользователем ask0n, 26 ноя 2010.

Статус темы:
Закрыта.
  1. ask0n

    ask0n

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

    Вот нашел еще интересный вариант:
    http://algolist.manual.ru/maths/graphs/shortpath/wave.php
    Также интересно было бы узнать наиболее оптимальный алгоритм для решения этой задачи, если максимальное количество подчиненных точек в каждом дереве от 10 до 100
     
Статус темы:
Закрыта.