Ең қысқа жиек ажыратылған жолдар алгоритмі

Кіріспе

Шеттерді бөлісетін ең қысқа жұп алгоритмі – компьютерлік желілерді маршруттау алгоритмі. Алгоритм берілген төбелер арасындағы ең қысқа шеттік жолдар жұбын құру үшін қолданылады. Бағытталмаған граф үшін G(V, E), ол былай сипатталады:

Берілген төбелер жұбы үшін ең қысқа жол алгоритмін іске қосыңыз.
Ең қысқа жолдың әрбір шетін (екі қарама-қарсы бағытталған доғаға тең) бастапқы төбеге бағытталған бір доғамен ауыстырыңыз.
Жоғарыдағы доғалардың әрқайсысының ұзындығын теріс етіңіз.
Ең қысқа жол алгоритмін іске қосыңыз (Ескерту: алгоритм теріс құндылықтарды қабылдауы керек).
Табылған екі жолдың бір-бірімен келісетін шеттерін жойыңыз және бірінші ең қысқа жолдағы қалған доғалардың бағытын кері бұрыңыз, осылайша оның әр доғасы енді мақсатты төбеге бағытталсын. Қажетті жолдар жұбының нәтижесі. Фордтың теріс доғалары бар кез келген жердегі (теріс циклдар болмаса) жалпы мақсаттағы ең қысқа жол алгоритміне қарағанда, Бхандари 4-қадамда қолданылатын екі түрлі алгоритм ұсынады. Бір алгоритм – дәстүрлі Дикстра алгоритмінің шағын өзгертілген нұсқасы, ал екіншісі – ендік бірінші іздеу (BFS) алгоритмі, ол Мур алгоритмінің түрі. Теріс доғалар тек бірінші ең қысқа жолда болғандықтан, трансформацияланған графта теріс цикл пайда болмайды (2 және 3-қадамдар). Теріс емес графта, өзгертілген Дикстра алгоритмі дәстүрлі Дикстра алгоритміне дейін тоғысып, осылайша жоғарыда аталған алгоритмнің 1-қадамында (және сондай-ақ BFS алгоритмінде) қолданылуы мүмкін.

Мысал

Шеттермен қиылыспайтын ең қысқа жұп алгоритмінің негізгі қадамдары төменде көрсетілген: А суретінде берілген бағытталмаған граф G(V, E) және оның қабырғаларының салмақтары көрсетілген. B суретінде А-дан Z-ға дейінгі есептелген ең қысқа жол ABCZ көрсетілген (қалың сызықтармен). C суретінде ең қысқа жолдың доғаларының керілуі және олардың теріс салмақтары көрсетілген. D суретінде C суретіндегі жаңа түрлендірілген граф бойынша А-дан Z-ға дейінгі ең қысқа ADCBZ жолы көрсетілген (бұл өзгертілген Дикстра алгоритмі (немесе BFS алгоритмі) арқылы анықталады, ол мұндай теріс доғалар үшін жарамды; мұндай түрлендірілген графтарда теріс циклдар болмайды). E суретінде бастапқы граф бойынша анықталған ең қысқа ADCBZ жолы көрсетілген. F суретінде ABCZ және ADCBZ жолдарына ортақ BC қабырғасын жойып, қалған қабырғаларды тиісті түрде топтастырғаннан кейін табылган ең қысқа шеттік жолдар жұбы (ABZ, ADCZ) көрсетілген.

Талқылау

Теріс емес графикте өзгертілген Дикстра алгоритмі дәстүрлі Дикстра алгоритмі сияқты жұмыс істейді. O(d) дәрежелі түйіндері бар графикте тиімділігі O(d|V|) болып табылады, ең нашар жағдайда, дәстүрлі Дикстра сияқты, O(|V|²) болады. Теріс қабырғалары бар шеттік ажыратылған ең қысқа жұп алгоритмінің түрлендірілген графигінде, өзгертілген Дикстра алгоритмінің 2a қадамында бұрын "тұрақты" деп белгіленген түйін 3a қадамында қайта қаралып, қайта белгіленуі және S жиымына (3b қадамы) қайта қосылуы мүмкін. Мұндай түрлендірілген графиктегі өзгертілген Дикстраның тиімділігі O(d²|V|) болады, ең нашар жағдайда O(|V|³) болады. Көптеген практикалық маңызы бар графиктер әдетте сиректеу болады, O(1) дәрежелі түйіндерге ие, онда түрлендірілген графикке қолданылатын өзгертілген Дикстра алгоритмінің тиімділігі O(|V|) (немесе эквивалентті, O(|E|)) болады. Шеттік ажыратылған ең қысқа жұп алгоритмі тиімділігі жағынан Suurballe алгоритмімен салыстырылады, ол жалпы алғанда O(|V|²) болады, себебі терiс құнмен қабырғаларды болдырмау үшін графты қайта салмақтауға қосымша түрлендіру қажет, бұл Дикстра алгоритмін ең қысқа жол қадамдарының екеуі үшін қолдануға мүмкіндік береді. Қайта салмақтау үшін бастапқы түйінде тамырланған ең қысқа жол ағашының толық құрылымын салу қажет. Осы қосымша графтық түрлендіруден бас тарту және оның орнына өзгертілген Дикстра алгоритмін пайдалану арқылы Бхандаридің тәсілі шашыраңқы графтар үшін тиімділік жоғалтпай, шеттік ажыратылған ең қысқа жұп алгоритмінің оңайлатылған нұсқасын ұсынады. Осы қарапайыы форма 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).