Algoritme de Johnson

El algoritme de Johnson és una forma de trobar el camí més curt entre tots els parells de vèrtiços d'un grafo dirigit dispers. Permet que les arestes tinguen pesos negatius, si ben no permet cicles de pes negatiu. Funciona utilisant l'algoritme de Bellman-Ford per a fer una transformació en el grafo inicial que elimina totes les arestes de pes negatiu, permetent per tant usar l'algoritme de Dijkstra en el grafo transformat. El seu nom ve de Donald B. Johnson, qui fora el primer en publicar la tècnica en 1977.

Descripció de l'algoritme

L'algoritme de Johnson consistix en els següents passos:

1. Primer s'afig un nou nodo q al grafo, conectat a cada u dels nodos del grafo per una aresta de pes zero.
2. En segon lloc, s'utilisa l'algoritme de Bellman-Ford, escomençant pel nou vèrtiç q, para determinara per a cada vèrtiç v el pes mínim h(v) del camí de q a v. Si en este pas es detecta un cicle negatiu, l'algoritme conclou.
3. Seguidament, a les arestes del grafo original se'ls canvia el pes usant els valors calculats pel algoritme de Bellman-Ford: una aresta de o a v en tamany w(o, v), dona el nou tamany w(o, v) + h(o) – h(v)
4. Per últim, per a cada nodo s s'usa l'algoritme de Dijkstra per a determinar el camí més curt entre s i els atres nodos, usant el grafo en pesos modificats.

En el grafo en pesos modificats, tots els camins entre un parell de nodos s i t tenen la mateixa cantitat h(s) – h(t) afegida a cada u d'ells, aixina que un camí que siga el més curt en el grafo original també és el camí més curt en el grafo modificat i viceversa. No obstant, pel modo en el que els valores h(v) són computats, tots els pesos modificats de les arestes són no negatius, assegurant llavors l'optimalidad dels camins trobats pel algoritme de Dijkstra. Les distàncies en el grafo original poden ser calculades a partir de les distàncies calculades pel algoritme de Dijkstra en el grafo modificat invertint la transformació realisada en el grafo.

Anàlisis de la complexitat

La complexitat temporal d'este algoritme, usant montículs de Fibonacci en l'implementació del algoritme de Dijkstra, és d'O(V²log V + VE): l'algoritme usa un temps d'O(VE) per a la fase Bellman-Ford de l'algoritme, i O(V log V + I) para cada una de les V instàncies realisades de l'algoritme de Dijkstra. Llavors, quan el grafo és dispers el temps total de l'algoritme pot ser menor que l'algoritme de Floyd-Warshall, que resol el mateix problema en un temps d'O(V³).

Referències

• Artículs de Donald B. Johnson (Publicacions d'ACM)
• Johnson, Donald B. (1977), "Efficient algorithms for shortest paths in sparse networks", Journal of the ACM
• ^{[enllaç trencat]}