Если у вас неположительные ребра, это может быть не дерево, например, для следующего графика и начиная с n1:
ВПервый проход:
- , посетив e1:
d[n2] = d[n1] + w[e1] = 1 & p[n2] = n1 - , посетив e2:
d[n3] = d[n2] + w[e2] = 1 & p[n3] = n2 - , посетив e3:
d[n4] = d[n3] + w[e3] = 1 & p[n4] = n3 - , посетив e4:
d[n2] = d[n4] + w[e4] = 1 & p[n2] = n4
и на всех остальных проходах это будет повторяться. так что в конце, если вы выполните итерации по предшествующему примеру, например, для n2, вы получите: n2 <- n4 <- n3 <- n2 <- n4 <- ...
Но я думаю, что если у вас нет неотрицательных ребер, это прекрасно работает.