[теория графов] Алгоритм поиска маршрута.

К кодовой базе graphviz посылать не надо, там много букв... Мне надо простенькое чтобы я за час прогу навалял...

> Читать теорию или выводить алгоритм самому не хочу.

Почему-то тут мне стало очень смешно. Я проиграл =(

Если представление связей в такой таблице неудобно, можно описать другую таблицу... Мне без разницы, солью линки в другую таблицу..

> Читать теорию или выводить алгоритм самому не хочу. Дайте ссылку на алгоритм в идеале блоксхему, можно код на любом языке, в идеале python...

Наслаждайся, оно там даже на python: http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%...

Всё же прошу ссылку для желающих почитать теорию.

graphviz

Я забил на теорию, пишу тупым перебором всех свичей и их линков пока не попаду на нужный свич, начиная с соседей как в алгоритме «поиск в ширину»...

Кто знает чтото лучше пишите... )

Читаю это http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC...

> Всё же прошу ссылку для желающих почитать теорию.

Что конкретно интересует? Просто в общем случае есть два алгоритма обхода: в ширину и в глубину. На их основе и создаются алгоритмы поиска циклов, маршрутов, компонент связности и т.д. Они оба элементарны(той же википедии хватит, чтобы суть понять).

Всю эту базу можно найти скажем в книге: http://lib.mexmat.ru/books/520

Всё доступно расписано + даны алгоритмы в псевдокоде. Хотя что под C++(Boost Graph Library), что под C#(скажем QuickGraph) есть готовые реализации, думаю и под многие другие языки это тоже есть готовое.

Возьму привяжу к http://www.boost.org/ пусть считает, хотя на питоне может тоже выгуглю чё...

Нет таки возьму какой то питоновский с гугла: «Dijkstra's algorithm python» )))

>в такой структуре между двумя любыми вершинами звёзд существует только один единственный путь.

Имхо в этом случае алгоритм Дейкстры будет оверкиллом. Юзай тупой поиск в глубину/ширину

Ну перекушу,а там решу :)

Это же блин дерево. Поиск глубину/ширину и больше ничего не надо

В глубену наверно предпочтительнее? Так есть больше вероятности быстрее попасть на конечный свич? Или мне так кажется?

Это зависит от топологии сети и начальной вершины, я бы взял метод в ширину, если исходить из твоих объяснений в первом посте.

Так смотри, что у тебя больше, глубина или ширина =) Если глубина большая, а ширина маленькая (разница на порядки) то лучше в ширину. А если ширина маленькая, а глубина большая, то в ширину =) Если величины одного порядка, то или без разницы, или можно рандомом выбирать алгоритм (но так я только в учебных проектах делал) =)

Дейкстра тут не оверкилл. Он просто здесь не причем. Пойму что весов нет. Более того тут и поиск в ширину в чистом виде не нужен. Надо использовать волновой алгоритм.

Я уж молчу, что поиск в глубину использовать для поиска пути это шизофрения и полный перебор.

Ха, почитал про этот волновой алгоритм. Это именно то, что я имел в виду, говоря «поиск в ширину» в контексте поиска пути в дереве (то есть в связном графе без циклов). А про поиск в глубину ты зря так. При малой глубине дерева он гораздо менее полный перебор, чем поиск в ширину.

Тьфу, блин. Надо читать сообщение перед отправкой. Но понятно же все, да?

Нет. Какая-то ахинея

Много чего интересует, решил подтянуть знания. Эта книга есть, но никак не доходит до неё очередь хода. Спасибо, +1 повод чтобы следующей начать её.

один раз разметить дерево как Nested Sets http://en.wikipedia.org/wiki/Nested_set_model далее любые маршруты ищутся элементарно и быстро

У меня древо сильно часто меняется.

Лучше скажите как мне используя алгоритм поиска в ширену записывать номера узлов чтобы потом легко можно было сформировать путь. А то с простой нумерации узлов путь не вытянешь...

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

>Я уж молчу, что поиск в глубину использовать для поиска пути это шизофрения и полный перебор.

Анон, ты пишешь ерунду =(

Ну да, спросоня чушь написал. Насчет поиска в глубину

>проиграл

Вали обратно на тиреч^Wсосач.