Need help for this stack overflow in Bellman-Ford algorithm

[Gyu-Ho Lee]

Hello gophers,

hope you having a great weekend.

I have this graph, from CLRS.

My Bellman-Ford algorithm implementation works well, returning false for the graph with negative edges.

http://play.golang.org/p/fFv_KvU_FZ

But when I try to backtrack the shortest path, I get the stack overflow error.

http://play.golang.org/p/CzbJKIV6SW

I use the same backtrack function for Dijkstra algorithm and it works with that algorithm.

The error message is like the following:

runtime stack:

runtime.throw(0x22fea0, 0x21820)

/tmp/sandbox/go/src/pkg/runtime/panic.c:471 +0xa0

runtime.newstack()

/tmp/sandbox/go/src/pkg/runtime/stack.c:295 +0x440

runtime.morestack()

/tmp/sandbox/go/src/pkg/runtime/asm_amd64p32.s:207 +0x80

goroutine 1 [stack split]:

main.(*Graph).TrackBellmanFord(0x105001a8, 0x1054c180, 0x1054c200, 0x1c15d000, 0x5b448c, ...)

/tmpfs/gosandbox-0dcd2156_dff9299a_c5c36ad9_8d86f949_e39cb98c/prog.go:130 fp=0xefec2100

main.(*Graph).TrackBellmanFord(0x105001a8, 0x1054c180, 0x1054c280, 0x1c15d000, 0x5b448a, ...)

/tmpfs/gosandbox-0dcd2156_dff9299a_c5c36ad9_8d86f949_e39cb98c/prog.go:134 +0x2a0 fp=0xefec2150

And the line 130 and 134 is where I run the tracking function recursively

func (G *Graph) TrackBellmanFord(source, target *Vertex, result []string, result_list *list.List) {

result = append(result, target.ID)

if len(target.Prev) != 0 && target.Prev[len(target.Prev)-1] != source {

result = append(result, target.Prev[len(target.Prev)-1].ID)

G.TrackBellmanFord(source, target.Prev[len(target.Prev)-1], result, result_list)

------

Could anybody point out what is wrong with my code? 

Or how would I debug this? 

The recursion seems to run forever in this case

, but don't understand how, since it works well with another algorithm.

I would appreciate if you can help!

[Tamás Gulácsi]

Maybe an infinite loop because of the negative efges an recursion?

[Gyu-Ho Lee]

Thanks, but the algorithm works even with the negative edges, as seen in this code

http://play.golang.org/p/OhjDqC97fj

I fixed it to check if in backtracking, I visit the node or not.

But now I am getting [Process Took Too Long] message.

http://play.golang.org/p/UouyGu5q6x

Does anyone know what makes this recursion go forever?

The previous code did not have enough condition to check but this one I check all the possible cases that can go forever but still getting the infinite loop.

[Gyu-Ho Lee]

I figured that out. I was not checking the duplicate source node visit.

For those who might wonder

This works...

http://play.golang.org/p/y0mF-MKFCB

Thanks!