Algoritmo de Johnson

Dado un grafo dirigido con n vértices (numerados del 0 al n-1) y una lista de aristas con pesos (que pueden ser negativos, pero sin ciclos negativos), implementa el Algoritmo de Johnson para encontrar las distancias mínimas entre todos los pares de vértices.

El algoritmo de Johnson combina:

1. Bellman-Ford desde un vértice virtual extra para calcular potenciales h[v].
2. Re-ponderación de aristas: w'(u,v) = w(u,v) + h[u] - h[v] (garantiza pesos no negativos).
3. Dijkstra desde cada vértice para obtener distancias re-ponderadas.
4. Corrección final: dist(u,v) = d'(u,v) - h[u] + h[v].

Parámetros

• n: número de vértices.
• edges: arreglo de tripletas [u, v, w] representando una arista dirigida de u a v con peso w.

Retorno

Una matriz n × n donde result[i][j] es la distancia mínima de i a j. Si j no es alcanzable desde i, usa 999999 como valor centinela.

Ejemplo

johnsonAllPairs(4, [[0,1,1],[0,2,4],[1,2,2],[1,3,5],[2,3,1]])
// [
//   [0, 1, 3, 4],
//   [999999, 0, 2, 3],
//   [999999, 999999, 0, 1],
//   [999999, 999999, 999999, 0]
// ]

Restricciones

• 1 <= n <= 100
• Los pesos pueden ser negativos pero no hay ciclos negativos.
• Si no hay arista entre dos vértices, la distancia es 999999.