Подскажите есть ли универсальный алгоритм для поиска нескольких кратчайших путей на графе

[karkotskidmitry]

Уважаемые ученые, помогите мне найти ответ, пожалуйсто!!!
 Существют множество алгоритмов, позволяющих определять ОДИН КРАТЧАЙШИЙ путь на графовой модели. Но мне необходимо определить несколько путей из разных исходных вершин в одну конечную.  Подскажите есть ли универсальный алгоритм, позволяющий определять несколько кратчайших путей на графе???
Заранее всем благодарен!!!

 

 

[folk]

Давно это было - могу ошибаться, но если вы построите минимальное остовное дерево (алгоритм Крускала например) то получите ответ на почти все вопросы о минимальных путях

[12d3]

Алгоритм Флойда-Уоршела.

[Ian]

Алгоритм Дейкстры. Проводить назад, то есть от фиксированной Вами конечной вершины расширять множество вершин с известными кратчайшими путями в нее, начиная с наименьших значений пути. Можно оборвать когда более длинные пути уже не интересуют. Есть ручная реализация, состоящая в последовательном заполнении простой таблицы (один преп учил своих студентов так, как в файле http://rghost.ru/60278340 , пункт 6-7, хотя большинство не так)
 

[karkotskidmitry]

Речь идет не об алгоритме Дейкстры и для общего случая - Форда-Беллмана, которые позволяют определить ЕДИНСТВЕННЫЙ кратчайший путь.
Предположим что граф это некая избытачная обобщенная структурная схема системы. Эта система может состоять из одного модуля (1-н путь от истока к стоку) или из n  модулей (n путей от, возможно разных, истоков к одному результату (продукту) - стоку). Но при построении из n модулей система будет оптимальной согласно выбранного критерия оптимальности по отношению, еслиб система состояла из одного модуля. Т.О. задача сводится к определению не только одного кратчайшего пути, а к поиску совокупности путей. Т.О. определяется не только состав структуры но и количество (n) модулей.
Есть ли для такой постановке задачи алгоритм решения на графовой модели? Если нет то как можно решить эту задачу применительно к графу?


 

[folk]

Вообще говоря вам дали правильный ответ - Алгоритм Флойда-Уоршела или Данцига.

[individ.an]

Наверное я никогда не пойму, чё же они там считают!
 
Задачу формулируют так запросто, а мне даже формулировка не понятна.
Ищут кратчайший путь - при этом не понятно  как этот путь дожен проходить. Через какие точки должен проходить. Меня всегда учили, что самый короткий это соеденить две точки прямой.
Наверное это для посвящённых - они в курсе какие точки надо исключать.
 
Но не понятно, если знаешь алгоритм который ищет кратчайший путь между двумя точками - в чём проблема взять его применить к каждой отдельной точке?
То же загадка!
Всегда когда читаешь описания таких алгоритмов - такое впечатление складывается, что они по моему не понимают, что говорят.
Просто банально переписывают друг у друга. Часто даже видно до буковки одинаковые обозначения.
 
Хотя это дело вкуса. Вот народ любит очень модульную арифметику. Сколько раз им не говори, что можно решить задачу проще и быстрей - без этого. Всё равно так считают.
Консерватизм - ничего не поделаешь.
Так и тут. Лучше использовать придуманные природой фрактальные - почти оптимальные алгоритмы - чем эту глупость.
Там всё проще - видишь это - делай то!
 

[folk]

Так вы найдите реализацию алгоритма, убедитесь что работает, и пользуйесь без понимания)
Кстати то что иногда лучше использовать более простой алгоритм чем оптимальный - тут вы совершенно правы. И задача линейного программирования тому вопиющий пример - симплекс метод кубичный а пользуются им ибо проще чем более оптимальные асимптотически. Фокус в том что на реальных данных зачастую симплекс метод ведет себя много лучше чем в худшем случае.
Насчет того что не понимают о чем говорят - извините, но вы сначала решите своим методом задачи тех размерностей о которых в статьях пишут. На игрушечных примерах все алгоритмы хороши..

[individ.an]

Source of the post Насчет того что не понимают о чем говорят - извините, но вы сначала решите своим методом задачи тех размерностей о которых в статьях пишут. На игрушечных примерах все алгоритмы хороши..

 
Так зачем мне надо решать случай 7-мерного пространства?
Хотя если алгоритм работает ему всё равно какая размерность.
На практике есть фактически 2 задачи.
Первая.
Выйти с одного места и прийти куда-то затратив минимальный путь. Там вообще ничего считать не надо. 
Решение приходит сразу как только посмотрел на карту.
Вторая - задача Водоноса.
На Ослика загрузили какое то количество воды. Надо развести по пунктам - в каждом выгружаем разное количество.
Нагрузка на Ослика - это произведение его массы + масса переносимой воды    умноженная на путь пройденым Осликом.
Нужно минимизировать нагрузку на животину.
Тут придётся подсчитать, но не так много.
 
Если есть возможность - предложите оптимальный и простой. Народ сложные методы крайне тяжело понимает.
Тем более если надо много считать.
Хотя все мои знакомые пользуются тем методом о котором говорю.
Это быстро, эффективно и понятно - почему так надо поступать.
При таких ценнах на бензин - приходится математику привлекать - ничего не поделаешь.
 
Только те алгоритмы о которых говорите - они годятся разве, что для Чубайса. 
В жизни очень частно в процессе поездки ситуация меняется. Поездка в какой то пункт отменяется или же надо наоборот надо будет заехать куда то дополнительно. 
Значит принимать решение будет человек - надо иметь инструкцию, что делать в случае форс мажорных обстоятельствах.
Хотя сами посудите - не будет же разносчик пиццы сидеть и считать. А потребность в оптимальных алгоритмах как раз у таких людей.

[folk]

Source of the post Хотя сами посудите - не будет же разносчик пиццы сидеть и считать. А потребность в оптимальных алгоритмах как раз у таких людей.

У него цена выбора неоптимального маршрута низка. Как правило либо на глазок либо перебором. Малые размерности мы можем взгляом окинуть.
Реально сложные задачи на оптимальность это другие -  сапры, компиляторы и например назначение выводов микросхемы  контактам чипа. Ну и глобальные экономические задачи наверное. Если вы с ними не сталкиваетесь то да можете использовать любой алгоритм. Но если у вас только сама задача час загружается в сапр, то хочется чуть чуть подумать и над алгоритмом в сторону оптимальности