увы но как  я и говорил код не мой

обобщенный поиск в ширину

эта функция не зависит от представления графа, для адаптации к конкретному представлению служит функция get_adjacent ();
реализация bfs не самая общая, но достаточная для наших целей: для каждой посещенной вершины вызывается пользовательская функция-посетитель $current(), куда передается ребро (текущая вершина и та, из которой мы сюда пришли).

реализация функции-посетителя для алгоритма поиска кратчайщих путей по Дейкстре:

она почти тривиальна, в качестве веса любого ребра используется единица (в вашем графе веса не указаны, поэтому я не стал усложнять).
в глобальных массивах $cost и $path хранятся стоимости(длины) путей и сами пути соответственно

что бы применить это к вашей структуре нужен адаптер. в данном случае он тривиален:


ну вот и все, остальное самостоятельно допилите
http://codepad.org/d2eGCrci

для минимизации пересадок измените вес для пересадки (уже говорили про это)


кстати, вам нужно минимум пересадок или минимальное время?

огромное спаисбо зхавтар буду разбираться
если что  надеюсь поможете но думаю все норм еще рас спс

Добавлено @ 20:08


вообще то и то  и то в зависимости  от выбора пользователя 
кстати как правельно задать  веса для пересадок?
как отдельный массив ? и проверять принадлежит ли дуга VU этому массиву и если да то  делатть не +1 а +много или как?

Это сообщение отредактировал(а) xber9 - 2.11.2012, 23:54

по разному можно. например, опциональным параметром (т.е. элемент массива смежности может быть массивом (станция, вес)
более правильно, думаю, задавать веса для всех ребер (значения времени в минутах, например), включая время пересадок. 

но если вводить вес, программу придется немного переделать: мой dijkstra_visitor() по сути relax_visitor(), они совпадают для невзвешенного графа, а для взвешенного графа dfs  bfs с обычной очередью недостаточно, нужно иметь очередь с приоритетами.

Добавлено @ 13:39

можно и так, можно добавить явные пути для пересадок, можно, как я выше написал. зависит от желаемого результата и возможных расширений в будущем. если приоритет пересадки делать заведомо большим, чем время обычного проезда до следующей станции, пересадки будут выбираться, только если нет другого пути.
для себя, например, я определил, что среднее время между станциями и среднее время одной пересадки - 2.5мин. это, конечно, не дает наименьшее число пересадок, но время предсказывает хорошо и дает быстрые пути. для бабушки, кторая не может бегать между станциями, пересадка может стоить и 10мин.

Это сообщение отредактировал(а) baldina - 3.11.2012, 14:27

извиняюсь но я практически ничего не понял  из этой фразы
где об этом можно почитать или может если для вас это не слишком затруднительно покажете как изменить ваш  пример ( конечно если не об очень многом прошу)
еще рас прошу прощения если очень сильно напрягаю и туплю  

Добавлено @ 13:48

идея со временем   кажется самое то  тк время пути тоже надо будет  подсчитывать

я  так понимаю вы предлагаете изменить исходные данные типа так


но тогда как менять фунцию ибо я как всегда не понимаю (не хватает математических знаний как я пологаю)

Это сообщение отредактировал(а) xber9 - 3.11.2012, 13:50

да, фраза не очень понятная))) и с ошибкой: не dfs, а bfs - поиск в ширину
в поиске в ширину в очередь заносятся смежные вершины, потом из очереди вынимаются и обрабатываются. если весов нет, длина пути соответствует числу проходимых вершин
если веса есть, нужно из очереди выбирать вершину с наименьшим весом(приоритетом), поэтому требуется очередь с приоритетами (это и будет алгоритм дейкстры).
в любом алгоритме поиска кратчайших путей (в т.ч. в простейшем на основе поиска в ширину) используется т.н. функция relax для релаксирования путей, т.е. поддержания списка кратчайших путей и их весов.
для очередей с приоритетами в php можно использовать класс SplMinHeap

любая книга по алгоритмам,
http://en.wikipedia.org/wiki/Breadth-first_search
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%82%D1%80%D1%8B


да, что-то типа этого.

Добавлено через 1 минуту и 9 секунд
будет время, попробую написать, но позже...

если будет возможность напишите плиз  ибо сам я не уверен что до конца разберусь

вот http://codepad.org/OoaxvDF9
это многословнее, чем раньше, но подходит для адаптации к разным представлениям графа и алгоритмам

Добавлено через 8 минут и 34 секунды
кстати, простейшая модификация первой реализации для работы с весами - просто перенести вызов $current:

Это будет некая разновидность алгоритма Беллмана-Форда. Для  графов без отрицательных весов этот алгоритм менее эффективен, чем Дейкстры, но для пары сотен вершин и ребер думаю разница несущественная.

большое спасибо очень выручил- буду постепенно разбираться
я правельно понимаю что для того чтобы  считался путь с минимумом пересадок достаточно значительно увеличить  вес пересадки а чтобы  искал просто кратчайший путь то надо обратно уменьшить вес

и еще вопрос ( так как еще не разобрался) как вывести на печать общий вес пути from - to

да. 
кстати, минимум пересадок может давать очень плохие пути. например, динамо-савеловская через тверскую. даже бабушка так не поедет.


содержится в 

я понимаю поэтому буду давать пользователю выбор   как ему  посчитать
мин времени или мин пеерсадок
>динамо-савеловская через тверскую 
я поеду так как инвалиду легче  дальше проезхать   чем ходить по переходам)
еще рас спасибо

НЕ охото начинать новую тему поэтому спрошу тут
переделал данные вот так

 где t1....t4 времена ( веса) для пересадок
далее при определнных условиях я делаю так



однако данные внутри описания графа ($graph)  отсались прежними а не =100

вопрос как переинициализоваровать граф чтобы  туда записались сотни ( надеюсь понятно  обьяснил)


Это сообщение отредактировал(а) xber9 - 4.11.2012, 23:22

или как по другому изменять веса для пересадок при определенных условиях

ситуация аналогична такой:


варианты решения:



а самый простой и правильный вариант вероятно такой: