El algoritmo de Johnson consiste en los siguientes pasos: En el grafo con pesos modificados, todos los caminos entre un par de nodos s y t tienen la misma cantidad h(s) – h(t) añadida a cada uno de ellos, así que un camino que sea el más corto en el grafo original también es el camino más corto en el grafo modificado y viceversa.
En la tercera imagen, se muestra el árbol de caminos mínimos calculado con el algoritmo de Bellman-Ford con q como vértice inicial, y los valores h(v) calculados para cada otro nodo como la longitud del camino más corto entre q y ese nodo.
A modo de ilustración, en dicha imagen solo aparecen los caminos que se tomarían para determinar cada valor h(v).
Nótese que todos estos valores h(v) no son positivos, porque q tiene una arista de unión con cada nodo de peso 0, y por tanto el camino más corto no puede ser mayor que ese valor.
En este grafo modificado, todos los pesos de las aristas son positivos y el camino más corto entre dos nodos cualesquiera usa la misma secuencia de aristas que en el camino más corto entre los mismos dos nodos en el grafo original.