La distancia δ(s, v) es el peso mínimo de un camino de s a v. Con pesos puede ser un entero, ∞ cuando no hay camino, o −∞ cuando algún camino pasa por un ciclo de peso negativo y se puede abaratar sin límite. Cada grafo trae una fuente s y varios vértices; hay que escoger la distancia de cada uno entre las opciones (un entero, ∞ o −∞) y después leer, vértice por vértice, el camino o el ciclo que la justifica.
Si el grafo no tiene ciclos negativos, ¿por qué un camino más corto no necesita repetir vértices?
Suponga un camino más corto de s a v que pasa dos veces por el mismo vértice x. El tramo entre las dos visitas es un ciclo C. Sin ciclos negativos, el peso de C es mayor o igual que cero. Si pesa cero, quitarlo deja un camino de s a v con el mismo costo y menos aristas. Si pesa más que cero, quitarlo deja un camino más barato, y entonces el original no era el más corto. En los dos casos hay un camino más corto sin vértices repetidos, y por eso tiene a lo sumo |V| − 1 aristas: es la razón de que |V| − 1 rondas de Bellman-Ford alcancen.