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 con pesos únicamente positivos y luego ejecutar el algoritmo de Dijkstra a partir de cada vértice. Si los pesos no son todos positivos, los redefinimos para poder reducirlos al primer caso.
El algoritmo de Johnson se compone 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 de 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 usando los valores calculados por el algoritmo 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 use el algoritmo de Dijkstra para determinar los caminos más cortos.
Ejemplo del algoritmo de Johnson:
