Алгоритм поиска двух непересекающихся кратчайших путей

Введение

Алгоритм поиска двух непересекающихся кратчайших путей — это алгоритм в области маршрутизации компьютерных сетей. Он используется для нахождения пары кратчайших путей без общих ребер между заданной парой вершин. Для неориентированного графа G(V, E) алгоритм формулируется следующим образом:

1. Запустить алгоритм поиска кратчайшего пути для заданной пары вершин.
2. Заменить каждое ребро кратчайшего пути (эквивалентное двум дугам, направленным в противоположные стороны) одной дугой, направленной к исходной вершине.
3. Присвоить каждой из вышеуказанных дуг отрицательную длину.
4. Запустить алгоритм поиска кратчайшего пути (Примечание: алгоритм должен поддерживать отрицательные веса).
5. Удалить общие ребра двух найденных путей и изменить направление оставшихся дуг на первом кратчайшем пути так, чтобы каждая дуга была направлена к целевой вершине. В результате получается искомая пара путей. Вместо универсального алгоритма Форда для кратчайшего пути, работающего с отрицательными дугами в любом месте графа (при условии отсутствия отрицательных циклов), Бхандари предлагает два различных алгоритма, любой из которых можно использовать на шаге 4. Один из алгоритмов является незначительной модификацией традиционного алгоритма Дейкстры, а другой, называемый алгоритмом поиска в ширину (BFS), является вариантом алгоритма Мура. Поскольку отрицательные дуги присутствуют только на первом кратчайшем пути, в преобразованном графе не возникает отрицательных циклов (шаги 2 и 3). В неотрицательном графе модифицированный алгоритм Дейкстры сводится к традиционному алгоритму Дейкстры и, следовательно, может быть использован на шаге 1 вышеописанного алгоритма (и аналогично алгоритм BFS).

Пример

Основные шаги алгоритма поиска двух непересекающихся кратчайших путей показаны ниже: на рисунке А представлен данный неориентированный граф G(V, E) с весами ребер. На рисунке B изображен вычисленный кратчайший путь ABCZ из A в Z (выделен жирным шрифтом). На рисунке C показано изменение направления дуг кратчайшего пути и присвоение им отрицательных весов. На рисунке D изображен кратчайший путь ADCBZ из A в Z, найденный в новом преобразованном графе, представленном на рисунке C (это определяется с использованием модифицированного алгоритма Дейкстры (или алгоритма BFS), применимого к графам с отрицательными весами дуг; в таком преобразованном графе не возникает отрицательных циклов). На рисунке E показан найденный кратчайший путь ADCBZ в исходном графе. На рисунке F показана найденная пара непересекающихся кратчайших путей (ABZ, ADCZ) после удаления общего ребра BC из путей ABCZ и ADCBZ и соответствующей группировки оставшихся ребер.

Обсуждение

В неотрицательном графе модифицированный алгоритм Дикстры функционирует как традиционный алгоритм Дикстры. В графе, характеризующемся вершинами со степенями O(d) (d < |V|), эффективность составляет O(d|V|), будучи O(|V|²) в худшем случае, как и в случае традиционного алгоритма Дикстры. В преобразованном графе алгоритма поиска кратчайших пар ребер без общих ребер, который содержит отрицательные дуги, заданная вершина, ранее "постоянно" помеченная на шаге 2a модифицированного алгоритма Дикстры, может быть пересмотрена и перемаркирована на шаге 3a и возвращена в набор вершин S (шаг 3b). Эффективность модифицированного алгоритма Дикстры в таком преобразованном графе становится O(d²|V|), будучи O(|V|³) в худшем случае. Большинство графов, представляющих практический интерес, обычно являются разреженными, имеющими степень вершины O(1), в этом случае эффективность модифицированного алгоритма Дикстры, применяемого к преобразованному графу, становится O(|V|) (или, эквивалентно, O(|E|)). Алгоритм поиска кратчайших пар ребер без общих ребер затем становится сопоставимым по эффективности с алгоритмом Суурбаля, который в общем случае имеет сложность O(|V|²), из-за дополнительного преобразования графа, которое перевешивает граф, чтобы избежать отрицательных весов дуг, позволяя использовать алгоритм Дикстры для обоих шагов поиска кратчайшего пути. Перевес требует построения всего дерева кратчайших путей, укорененного в исходной вершине. Обходя это дополнительное преобразование графа и используя вместо этого модифицированный алгоритм Дикстры, подход Бхандари приводит к упрощенной версии алгоритма поиска кратчайших пар ребер без общих ребер без существенной потери эффективности, по крайней мере, для разреженных графов. Получающаяся простая форма также легко расширяется до алгоритмов поиска K (>2) непересекающихся путей и их вариаций, таких как частично непересекающиеся пути, когда полная непересекаемость отсутствует, а также к графам с ограничениями, с которыми сталкивается сетевой специалист в более сложных реальных сетях. Версия алгоритма поиска пар кратчайших путей без общих вершин получается путем разделения каждой вершины (за исключением исходной и целевой вершин) первого кратчайшего пути на шаге 3 алгоритма, соединения пары разделенных вершин дугой с нулевым весом (направленной к исходной вершине) и замены любого инцидентного ребра двумя дугами противоположного направления, одна из которых инцидентна вершине разделенной пары (ближе к исходной вершине), а другая дуга исходит из другой вершины. Версии для K (>2) получаются аналогичным образом, например, вершины кратчайшей пары ребер без общих ребер (за исключением исходной и целевой вершин) разделяются, причем вершины в каждой разделенной паре соединяются друг с другом дугами нулевого веса, а также внешние ребра соединяются аналогичным образом [8][9]. Алгоритмы, представленные для ненаправленных графов, также распространяются на направленные графы и применимы в целом к любой задаче (в любой технической дисциплине), которая может быть смоделирована как граф вершин и ребер (или дуг).

In a nonnegative graph, the modified Dijkstra algorithm functions as the traditional Dijkstra algorithm. In a graph characterized by vertices with degrees of O(d) (d<|V|), the efficiency is O(d|V|), being O(|V|2), in the worst case, as in the traditional Dijkstra's case. In the transformed graph of the edge disjoint shortest pair algorithm, which contains negative arcs, a given vertex previously "permanently" labeled in Step 2a of the modified Dijkstra algorithm may be revisited and relabeled in Step 3a, and inserted back in vertex set S (Step 3b). The efficiency of the modified Dijkstra in such a transformed graph becomes O(d2|V|), being O(|V|3) in the worst case. Most graphs of practical interest are usually sparse, possessing vertex degrees of O(1), in which case the efficiency of the modified Dijkstra algorithm applied to the transformed graph becomes O(|V|) (or, equivalently, O(|E|)). The edge disjoint shortest pair algorithm then becomes comparable in efficiency to the Suurballe's algorithm, which in general is of O(|V|2) due to an extra graph transformation that reweights the graph to avoid negative cost arcs, allowing Dijkstra's algorithm to be used for both shortest path steps. The reweighting requires building the entire shortest path tree rooted at the source vertex. By circumventing this additional graph transformation, and using the modified Dijkstra algorithm instead, Bhandari's approach results in a simplified version of the edge disjoint shortest pair algorithm without sacrificing much in efficiency at least for sparse graphs. The ensuing simple form further lends itself to easy extensions to K (>2) disjoint paths algorithms and their variations such as partially disjoint paths when complete disjointness does not exist, and also to graphs with constraints encountered by a practicing networking professional in the more complicated real life networks. The vertex disjoint version of the above edge disjoint shortest pair of paths algorithm is obtained by splitting each vertex (except for the source and destination vertices) of the first shortest path in Step 3 of the algorithm, connecting the split vertex pair by a zero weight arc (directed towards the source vertex), and replacing any incident edge with two oppositely directed arcs, one incident on the vertex of the split pair (closer to the source vertex) and the other arc emanating from the other vertex. The K (>2) versions are similarly obtained, e. g., the vertices of the shortest edge disjoint pair of paths (except for the source and destination vertices) are split, with the vertices in each split pair connected to each other with arcs of zero weight as well as the external edges in a similar manner[8][9]. The algorithms presented for undirected graphs also extend to directed graphs, and apply in general to any problem (in any technical discipline) that can be modeled as a graph of vertices and edges (or arcs).