Un eficiente algoritmo para resolver el problema de ruta más corta de fuente única. Los pesos pueden ser negativos. El algoritmo inicializa la distancia al vértice fuente a 0 y todos los demás vértices a ∞. Entonces hace V-1 pases (V es el número de vértices) sobre todos los bordes modificando, o actualizando, la distancia hasta el destino de cada borde. Finalmente comprueba cada borde otra vez para detectar ciclos de peso negativo, en cuyo caso devuelve un resultado 'false'. La complejidad del tiempo es O(VE), donde E es el número de bordes.