Typing out destructive weight cycle many times is form of annoying, so for the remainder of the query I’ll abbreviate it to NWC.
I am writing an optimized model of Bellman-Ford’s Shortest Path Algorithm on a directed, weighted graph. Once I give it an everyday graph with no NWC’s, it really works high-quality, and finds the reply appropriately. However after I give it a NWC, it loops perpetually. So, I put a system into the implementation the place it finds out if there’s a NWC, which it does appropriately, however now I am caught on what to do as soon as I discover it.
My first thought was to only go on commonly whereas setting each vertex within the cycle to destructive infinity, however each single vertex after that turns into destructive infinity too, and shortly sufficient, an enormous chunk of the graph turns into destructive infinity and I am getting bugs left and proper as a result of I am subtracting to destructive infinity, including to destructive infinity, whereas additionally setting the gap to destructive infinity. I technically might repair all of the bugs, however then lot’s of useful info on the opposite vertices is misplaced due to one little NWC.
My subsequent thought was to only terminate this system, however then once more lot’s of knowledge is misplaced on the opposite vertices.
So, what’s the appropriate motion to be taken whenever you discover a NWC?