Johnson'ın algoritması - Johnson's algorithm

Johnson'ın algoritması
Sınıf	Tüm çiftler için en kısa yol problemi (ağırlıklı grafikler için)
Veri yapısı	grafik
En kötü durum performansı

Johnson algoritması bulmak için bir yöntemdir kısa yolları arasındaki tüm node çiftleri bir in kenar ağırlıklı yönlendirilmiş grafik . Bazı kenar ağırlıklarının negatif sayılar olmasına izin verir , ancak negatif ağırlık döngüleri mevcut olamaz . Tüm negatif ağırlıkları ortadan kaldıran giriş grafiğinin dönüşümünü hesaplamak için Bellman-Ford algoritmasını kullanarak çalışır ve dönüştürülmüş grafikte Dijkstra'nın algoritmasının kullanılmasına izin verir . Adını, tekniği ilk kez 1977'de yayınlayan Donald B. Johnson'dan almıştır .

Benzer bir yeniden ağırlıklandırma tekniği, negatif olmayan kenar ağırlıkları olan bir grafikte aynı iki köşe arasında minimum toplam uzunlukta iki ayrık yol bulmak için Suurballe'nin algoritmasında da kullanılır .

Algoritma açıklaması

Johnson'ın algoritması aşağıdaki adımlardan oluşur:

İlk olarak, grafiğe sıfır ağırlıklı kenarlarla diğer düğümlerin her birine bağlanan yeni bir düğüm $q$ eklenir .
İkinci olarak, Bellman-Ford algoritması yeni tepe başlayarak kullanılan $q$ , her tepe için bulmak, $hacim$ en az ağırlıkça $h (v)$ bir yolun gelen $q$ için $v$ . Bu adım negatif bir döngü tespit ederse, algoritma sonlandırılır.
Bellman-Ford algoritması tarafından hesaplanan değerler kullanılarak yeniden ağırlıklandırmalı orijinal grafik kenarları Sonraki: bir kenar $u$ için $v$ , uzunluğunda olan , yeni bir uzunluk verilir $ağırlık$ $($ $u$ $,$ $v$ $) +$ $H$ $($ $u$ $-)$ $h$ $($ $v$ $)$ . ${\görüntüleme stili w(u,v)}$
Son olarak, $q$ kaldırılır ve Dijkstra'nın algoritması , yeniden ağırlıklı grafikteki her bir $s$ düğümünden diğer her bir köşeye en kısa yolları bulmak için kullanılır . Orijinal grafikteki mesafe daha sonra Dijkstra'nın algoritması tarafından döndürülen mesafeye $h$ $($ $v$ $) -$ $h$ $($ $u$ $)$ eklenerek her $D$ ( $u$ , $v$ ) mesafesi için hesaplanır .

Örnek

Johnson'ın algoritmasının ilk üç aşaması aşağıdaki resimde gösterilmektedir.

Çizimin solundaki grafikte iki negatif kenar var, ancak negatif döngü yok. Merkezi bir grafik, yeni tepe $q$ , ile Bellman-Ford algoritması tarafından hesaplanan şekilde, bir kısa yol ağaç $q$ tepe noktasını başlangıç maddesi olarak, ve değerler $h (v)$ en kısa yol uzunluğu gibi bir başka düğüm hesaplanmış $q$ edilene düğüm. Bu değerlerin hepsinin pozitif olmadığına dikkat edin, çünkü $q'nun$ her köşe için uzunluk-sıfır kenarı vardır ve en kısa yol bu kenardan daha uzun olamaz. Sağ tarafta her bir kenar ağırlığı değiştirilmesi ile de meydana yeniden ağırlıklandırmalı grafiği gösterilmektedir göre $ağırlık$ $($ $u$ $,$ $v$ $) +$ $H$ $($ $u$ $) -$ $h$ $($ $v$ $)$ . Bu yeniden ağırlıklı grafikte, tüm kenar ağırlıkları negatif değildir, ancak herhangi iki düğüm arasındaki en kısa yol, orijinal grafikteki aynı iki düğüm arasındaki en kısa yol olarak aynı kenar dizisini kullanır. Algoritma, yeniden ağırlıklı grafikteki dört başlangıç düğümünün her birine Dijkstra algoritmasının uygulanmasıyla sona erer. ${\görüntüleme stili w(u,v)}$

doğruluk

Yeniden ağırlıklı grafikte, bir çift $s$ ve $t$ düğüm arasındaki tüm yollara aynı miktarda $h (s) - h (t)$ eklenir. Önceki ifade şu şekilde ispatlanabilir: $p$ bir yol olsun. Yeniden ağırlıklandırılmış grafikteki ağırlığı W, aşağıdaki ifadeyle verilir: ${\görüntüleme stili st}$

{\bigl (}w(s,p_{1})+h(s)-h(p_{1}){\bigr )}+{\bigl (}w(p_{1},p_{) 2})+h(p_{1})-h(p_{2}){\bigr )}+...+{\bigl (}w(p_{n},t)+h(p_{n} )-h(t){\bigr )}.

Her biri , önceki parantez içindeki ifadede tarafından iptal edilir ; bu nedenle, W için aşağıdaki ifadeyle kalıyoruz : $+h(p_{i})$ $-h(p_{i})$

{\bigl (}w(s,p_{1})+w(p_{1},p_{2})+...+w(p_{n},t){\bigr )}+ h(s)-h(t)

Parantez içindeki ifade, orijinal ağırlıktaki p'nin ağırlığıdır.

Yeniden ağırlıklandırma, her yolun ağırlığına aynı miktarı eklediğinden, yalnızca yeniden ağırlıklandırmadan sonra en kısa yol olması durumunda, yol orijinal ağırlıklandırmadaki en kısa yoldur. Bir kısa yol ait kenarların ağırlık q herhangi bir düğüme sıfırdır ve en kısa yollar dolayısıyla uzunlukları q yeniden ağırlıklandırmalı grafik sıfır olması için her bir düğüm; ancak yine de en kısa yollar olarak kalırlar. Bu nedenle, herhangi bir olumsuz kenarlar olabilir: kenarı ise UV sonra yeniden ağırlıklandırma sonra negatif bir ağırlığa, sıfır uzunlukta bir yol vardı q için u olumsuz bir uzunlukta bir yol oluşturacak, bu kenar ile birlikte q için v gerçeği bu çelişen, bütün çıkıntılar sıfır mesafeye sahip q . Negatif kenarların olmaması, Dijkstra'nın algoritması tarafından bulunan yolların optimalliğini sağlar. Orijinal grafikteki mesafeler, yeniden ağırlıklandırma dönüşümünü tersine çevirerek yeniden ağırlıklı grafikte Dijkstra'nın algoritması tarafından hesaplanan mesafelerden hesaplanabilir. ${\görüntüleme stili st}$

analiz

Zaman karmaşıklığı kullanarak bu algoritmanın, Fibonacci yığınlarını Dijkstra'nın algoritma uygulanmasında olduğu : algoritma kullanan algoritma Bellman-Ford aşaması için zaman ve her biri için Dijkstra'nın algoritmasının örneklemesi. Bu nedenle, grafik seyrek olduğunda, toplam süre , aynı sorunu zamanda çözen Floyd-Warshall algoritmasından daha hızlı olabilir . $O(|V|^{2}\log |V|+|V||E|)$ $O(|V||E|)$ $O(|V|\log |V|+|E|)$ ${\görüntüleme stili |V|}$ $O(|V|^{3})$