MAXimal | |
добавлено: 10 Sep 2010 16:13 Содержание [скрыть] Кратчайшие пути фиксированной длины, количества путей фиксированной длиныНиже описываются решения этих двух задач, построенные на одной и той же идее: сведение задачи к возведению матрицы в степень (с обычной операцией умножения, и с модифицированной). Количество путей фиксированной длиныПусть задан ориентированный невзвешенный граф Будем считать, что граф задан матрицей смежности, т.е. матрицей Очевидно, что в таком виде матрица смежности графа является ответом на задачу при Решение будем строить итеративно: пусть ответ для некоторого Легко заметить, что записанная выше формула — не что иное, как произведение двух матриц Таким образом, решение этой задачи можно представить следующим образом: Осталось заметить, что возведение матрицы в степень можно произвести эффективно с помощью алгоритма Бинарного возведения в степень. Итак, полученное решение имеет асимптотику Кратчайшие пути фиксированной длиныПусть задан ориентированный взвешенный граф Будем считать, что граф задан матрицей смежности, т.е. матрицей Очевидно, что в таком виде матрица смежности графа является ответом на задачу при Решение будем строить итеративно: пусть ответ для некоторого Внимательно посмотрев на эту формулу, легко провести аналогию с матричным умножением: фактически, матрица где операция Таким образом, решение этой задачи можно представить с помощью этой операции умножения следующим образом: Осталось заметить, что возведение в степень с этой операцией умножения можно произвести эффективно с помощью алгоритма Бинарного возведения в степень, поскольку единственное требуемое для него свойство — ассоциативность операции умножения — очевидно, имеется. Итак, полученное решение имеет асимптотику Обобщение на случай, когда требуются пути длины, не более чем заданная длинаОписанные выше решения решают задачи, когда требуется рассматривать пути определённой, фиксированной длины. Однако эти же решения можно приспособить и для решения задач, когда требуется рассматривать пути, содержащие не более чем заданное число рёбер. Сделать это можно, немного модифицировав входной граф. Например, можно раздвоить каждую вершину: для каждой вершины Решив на модифицированном графе задачу о поиске путей фиксированной длины, ответы на исходную задачу будут получаться как ответы между вершинами
|