En un grafo disperso, el algoritmo de Johnson puede lograr lo mismo en tiempo formula_55, y si el grafo es sin pesos, se puede lograr en tiempo formula_56 y espacio formula_57 utilizando el algoritmo de Brandes.