Content deleted Content added
WP:COMPUTING Tagging ( False Postive ?? ) :(Plugin++) Added {{WikiProject Computing}}. |
|||
Line 119:
Title says it all really. Is a negative cycle one in which every edge is -vely weighted, or is it one in which the overall path length is -ve? <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/24.153.207.149|24.153.207.149]] ([[User talk:24.153.207.149|talk]]) 00:22, 10 June 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
:Okay, we've had enough questions about negative cycles now that I think this could be expanded. The question is where to do it - I think the most appropriate place is in the general article about shortest path algorithms, and then we can link it from here. The brief answers are: a negative cycle is a cycle with total weight negative, and the behavior of a shortest path algorithm on a graph with negative cycles depends on the algorithm. It may fail to terminate; if it does terminate, it will return a valid result for graphs containing negative cycles, which doesn't make sense because such graphs have no shortest path between any two nodes both reachable from the negative cycle (you can achieve arbitrarily short paths by following the cycle). [[User:Dcoetzee|Dcoetzee]] 22:31, 10 June 2008 (UTC)
::In my opinion an article about "Negative Cycles" is needed, it could then elaborate on algorithms commonly used for such thing such as this one and the [[Bellman-Ford algorithm]] and this page could link to that article instead.
==C Implementation==
| |||