Кратчайший путь между двумя узлами графа, заданного матрицей смежности
не судьба запомнить какие релаксации флойд делал? по одним расстояниям ничего уже не найти
Очень даже найти. Только сложность будет количество вершин * длина пути. У тебя есть расстояние от A до B, тогда за A следует тот ее сосед X, для которого r(A, B) = AX + r(X, B причем подойдет любой удовлетворяющий этому соотношению сосед. Ищется перебором всех соседей. Так продолжаешь пока не придешь в B. Для этого не нужно равенство весов всех ребер, достаточно положительность весов всех циклов, то есть существования и конечности кратчайших путей
зашибись чо. а если сохранить для каждой пары среднюю вершину то пути стоятся за О от длины пути
зашибись чо. а если сохранить для каждой пары среднюю вершину то пути стоятся за О от длины путиЕсли узлы графа лежат в вершинах правильного многогранника, ребра повторяют ребра многогранника, то сколько надо памяти, чтобы сохранить срединные точки? Это даже без хорд. Дихотомия не вариант короче.
На самом деле достаточно той же матрицы расстояний, только вместо расстояния держать следующую вершину в кратчайшем пути, то есть на пересечении вершин A и B держать в матрице вершину X. В этом случае и путь, и расстояние восстанавливаются за время "длина пути".
Вмешаюсь в ученый спор: так как эту задачу решать-то?
Так, как предложено в 3-м посте.
На самом деле достаточно той же матрицы расстояний, только вместо расстояния держать следующую вершину в кратчайшем пути, то есть на пересечении вершин A и B держать в матрице вершину X. В этом случае и путь, и расстояние восстанавливаются за время "длина пути".Только не совсем следующую. Когда алгоритм обновляет путь от a до b строя путь через вершину m нужно сохранить m. Путь восстанавливается рекунсивно path(a, b) = path(a, m) + path(m, b)
Это уже оптимизации на случай, если тебе надо, например, частично восстанавливать путь. Типа в качестве m выступает вершина с максимальным l(a,m) + l(m,b) по какой-то метрике l. В этом случае быстро восстанавливается грубый путь. А для полного пути следующая вершина удобнее же.
а, ну да. матрица следующих вершин тоже элементарно строится.
Всем спасибо, метод, указанный в 3 сообщении, действительно работает.
Оставить комментарий
5065584
Есть граф, заданный матрицей смежности; для него есть матрица кратчайших расстояний, вычисленная алгоритмом Флойда-Уоршела. Все ребра графа имеют одинаковый вес, все вершины перенумерованы. Нужно проложить кратчайший путь между двумя данными вершинами, получив его в виде списка номеров вершин лежащих от начальной до конечной. Как это делается?