Cómo encontrar fmax usando el algoritmo de Johnson

El proceso es el siguiente:

1. Construir un gráfico dirigido.

2. Agregue un nuevo nodo virtual al gráfico dirigido construido, conecte cada punto a partir de este nodo virtual y establezca el peso en 0.

3. Utilice el algoritmo de Bellman-Ford para calcular la distancia más corta desde el nuevo nodo virtual a cada punto y colóquelo dentro del nodo.

4. Reasigne cada borde. La fórmula de asignación es el peso original + el valor dentro del nodo del punto inicial - el valor dentro del nodo final.

5. Elimine los nodos virtuales y el gráfico restante se colocará en el gráfico de Dijkstra.

6. Ejecute el algoritmo de Dijkstra, seleccione un punto como punto de partida cada vez y calcule la distancia más corta desde este punto a otros puntos. Después de cada cálculo, se gira el nodo inicial y se obtiene una matriz n * n, donde n es el número de puntos y el valor en la matriz es la ruta más corta.

7. La matriz de resultado es igual a cada valor de la matriz obtenida por el algoritmo de Dijkstra más el valor dentro del nodo final de la ruta menos el valor dentro del nodo en el punto inicial de la ruta.