Ответы:
> пути от первой вершины ко всем.
проблема в том, что нет четких критериев, по которым можно оценить "расстоняие" до того, как оно становится известным. Следовательно, все разновидности ветвей и границ упираются в этот критерий.
Подобные задачи исследуются в системах ИИ - алгоритмы поиска между двумя графами... Но чаще всего просто юзается жадный алгоритм поверх дейкстры (поиск вглубину).
2Каракуль: обход всех бывает слишком трудоемким. Например: навигация в крупном городе. Есть надежные алгоритмы, которые отсекают лишние пути (метод ветвей и границ во всех видах).
Уважаемый safright, Алгоритм поиска минимального остовного дерева вас устроит ;))))
-создаем массив и первым элементом устанавливаем первую вершину
-помечаем вершину как рассмотренную
-запихиваем массив в стек
-в цикле пока стек не пуст
-выпихиваем из стека массив
-у последнего элемента в массиве просматриваем соседние вершины
-если это вторая вершина - кратчайший путь найден
-если это помеченная вершина - пропускаем ее
-если это не помеченная вершина - копируем массив и к добавляем вершину в конец
-запихиваем копию в стек
-если все вершины помечены, а вторая вершина не достигнута - граф не связный и вершины находятся в разных подграфах
SETdream, я-т все это понимаю и знаю (обязанность, куда без нее). Но фишка-то в том, что эти алгоритмы ориентированы на поиск всех кратчайших путей ;) Есть разница между "найти кратчайший путь между двумя вершинами графа" и "найти минимальное остовное дерево графа", и она в том, что в большинстве частных случаев нужно не все дерево, а только его мелкая часть. Экзампл: поиск в логистической схеме, когда нужно доставить груз между соседними региаонами, а карта есть для всей страны. Нужна эвристика, которая это обработает. (Впрочем можно составить минимальное остовное дерево для статического графа и потом его юзать на радость всем.. но ведь это от задачи зависит)
Каким боком тут минимальное остовное дерево?
С каким пор алгоритм Дейкстры стал сложен в реализации?
15 лет назад