Johnsons algoritm

Johnsons algoritm

Klass	Kortaste vägproblem för alla par (för viktade grafer)
Datastruktur	Graf
Prestanda i värsta fall	$O(|V|^{2}\log |V|+|V||E|)$

För schemaläggningsalgoritmen med samma namn, se schemaläggning för jobbbutik .

Johnsons algoritm är ett sätt att hitta de kortaste vägarna mellan alla par av hörn i en kantviktad riktad graf . Det tillåter att några av kantvikterna är negativa siffror , men inga negativa viktcykler kan förekomma. Det fungerar genom att använda Bellman–Ford-algoritmen för att beräkna en transformation av ingångsgrafen som tar bort alla negativa vikter, vilket gör att Dijkstras algoritm kan användas på den transformerade grafen. Den är uppkallad efter Donald B. Johnson , som först publicerade tekniken 1977.

En liknande omviktningsteknik används också i Suurballes algoritm för att hitta två disjunkta banor med minsta totala längd mellan samma två hörn i en graf med icke-negativa kantvikter.

Algoritmbeskrivning

Johnsons algoritm består av följande steg:

1. läggs en ny nod q till grafen, kopplad med nollviktskanter till var och en av de andra noderna.
2. För det andra används Bellman–Ford-algoritmen , utgående från den nya vertexen q , för att för varje vertex v hitta minimivikten h ( v ) för en väg från q till v . Om detta steg upptäcker en negativ cykel, avslutas algoritmen.
3. Därefter vägs kanterna på den ursprungliga grafen om med hjälp av värden som beräknats av Bellman–Ford-algoritmen: en kant från u till v , med längden $w(u,v)$ , ges den nya längd w ( u , v ) + h ( u ) − h ( v ) .
4. Slutligen tas q bort, och Dijkstras algoritm används för att hitta de kortaste vägarna från varje nod s till varannan vertex i den omvägda grafen. Avståndet i den ursprungliga grafen beräknas sedan för varje avstånd D ( u , v ), genom att addera h ( v ) − h ( u ) till avståndet som returneras av Dijkstras algoritm.

Exempel

De tre första stegen i Johnsons algoritm visas i illustrationen nedan.

Grafen till vänster i illustrationen har två negativa kanter, men inga negativa cykler. Mittdiagrammet visar den nya vertexen q , ett kortaste vägträd som beräknats av Bellman–Ford-algoritmen med q som startpunkt, och värdena h ( v ) beräknade vid varje annan nod som längden på den kortaste vägen från q till den nod. Observera att alla dessa värden är icke-positiva, eftersom q har en längd-noll kant till varje vertex och den kortaste vägen får inte vara längre än den kanten. Till höger visas den omvägda grafen, bildad genom att ersätta varje kantvikt $w(u,v)$ med w ( u , v ) + h ( u ) − h ( v ) . I denna omvägda graf är alla kantvikter icke-negativa, men den kortaste vägen mellan två noder använder samma sekvens av kanter som den kortaste vägen mellan samma två noder i den ursprungliga grafen. Algoritmen avslutas med att tillämpa Dijkstras algoritm på var och en av de fyra startnoderna i den omvägda grafen.

Rätthet

I den omvägda grafen har alla vägar mellan ett par s och t av noder samma kvantitet h ( s ) − h ( t ) lagt till sig. Det föregående påståendet kan bevisas på följande sätt: Låt p vara en $st$ sökväg. Dess vikt W i den omvägda grafen ges av följande uttryck:

${\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 )}.$

Varje $+h(p_{i})$ avbryts av $-h(p_{i})$ i föregående uttryck inom hakparenteser därför har vi följande uttryck för W :

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

Uttrycket inom parentes är vikten av p i den ursprungliga viktningen.

Eftersom omviktningen lägger till samma mängd till vikten av varje $st$ väg, är en väg den kortaste vägen i den ursprungliga viktningen om och bara om den är en kortaste väg efter omviktning. Vikten av kanter som hör till en kortaste väg från q till valfri nod är noll, och därför blir längden på de kortaste vägarna från q till varje nod noll i den omvägda grafen; men de är fortfarande de kortaste vägarna. Därför kan det inte finnas några negativa kanter: om kant uv hade en negativ vikt efter omviktningen, så skulle nolllängdsbanan från q till u tillsammans med denna kant bilda en negativ längdbana från q till v , vilket motsäger det faktum att alla hörn har noll avstånd från q . Avsaknaden av negativa kanter säkerställer optimaliteten för de vägar som hittas av Dijkstras algoritm. Avstånden i den ursprungliga grafen kan beräknas från avstånden som beräknats med Dijkstras algoritm i den omvägda grafen genom att vända omviktningstransformationen.

Analys

Tidskomplexiteten för denna algoritm, med användning av Fibonacci-högar i implementeringen av Dijkstras algoritm, är $log |V|+|V||E|)}$$O(|V|^{2$ \ : Algoritmen använder $O(|V||E|)$ tid för Bellman–Ford-steget i algoritmen, och $O(|V|\log |V|+|E|)$ för var och en av $|V|$ instansieringar av Dijkstras algoritm. Således, när grafen är gles , kan den totala tiden vara snabbare än Floyd–Warshall-algoritmen , som löser samma problem i tiden $O(|V|^{3})$ .

externa länkar

• Boost: Alla par kortaste vägarna