Algoritmo de Johnson
El algoritmo de Johnson calcula los caminos más cortos para cualquier par de vértices en el grafico. el tiene un buen complejidad para gráficos dispersos (pocas aristas en comparación con el número de vértices).
Utiliza los algoritmos de Dijkstra y botones vadoy devuelve la matriz de ponderaciones de ruta más corta o la afirmación de que el gráfico tiene una ruta de ponderación negativa.
La técnica utilizada consiste en volver al caso solo con pesos positivos, luego ejecutar el algoritmo de Dijkstra partiendo de cada vértice. Si los pesos no son todos positivos, los redefinimos para poder reducirlos al primer caso.
El algoritmo de Johnson consta de los siguientes pasos:
- Agregar un nuevo nodo q al gráfico y conecte este nodo mediante arcos de peso cero a todos los demás nodos.
- Utilice el algoritmo Bellman-Ford a partir del nuevo nodo q para determinar, para cada vértice v, el peso mínimo h(v) de un camino de q Para v. Si se detecta un ciclo negativo, el algoritmo se detiene en caso de falla.
- Responder los arcos del gráfico inicial utilizando los valores calculados por el algoritmo de Bellman-Ford: un arco de tu Para v, cuyo peso o longitud anterior es el número w (u, v), tiene para una nueva longitud el número no negativo w (u, v) + h (u) - H v).
- Quitar la tapa q y utilice el algoritmo de Dijkstra para determinar los caminos más cortos.
Ejemplo del algoritmo de Johnson:
ES 
FR 
EN