{"id":41,"date":"2011-08-30T18:04:23","date_gmt":"2011-08-30T18:04:23","guid":{"rendered":"http:\/\/learninglover.com\/blog\/?p=41"},"modified":"2011-09-01T17:33:08","modified_gmt":"2011-09-01T17:33:08","slug":"bellman-ford-algorithm","status":"publish","type":"post","link":"https:\/\/learninglover.com\/blog\/index.php\/2011\/08\/30\/bellman-ford-algorithm\/","title":{"rendered":"Bellman-Ford Algorithm"},"content":{"rendered":"<p>I just finished a script which executes the Bellman-Ford Algorithm on a randomly generated directed graph (possibly with negative arcs). It can be accessed <a href=\"http:\/\/www.learninglover.com\/examples.php?id=7\">here<\/a>.<\/p>\n<p>The Bellman Ford algorithm is another shortest path algorithm. Unlike Dijkstra&#8217;s algorithm, though, this algorithm can handle edges with negative weights and detect negative cycles in a graph. Negative cycles are important because in a graph with negative cycles, there is no shortest path to some nodes since a negative cycle can be iterated an infinite number of times.<\/p>\n<p>The algorithm works by initially setting the distance from the source node to all other nodes to be infinity. The distance to the source is then updated to be 0 since we are already there.<br \/>\nNext we proceed through each edge (u, v) and check the condition that if the distance to u plus the weight of the edge (u, v) is less than the distance to the node v, then we have just found a shorter route to v.<\/p>\n<p>This condition on the edges only needs to be checked at most |V| times for each edge since any path will contain at most |V| edges, which means that the distance of a node can be updated at most |V| times.<\/p>\n<p>If after |V| times there is still a node whose weight can be updated, it signifies the existence of a negative weight cycle and the Bellman-Ford will show that this cycle exists, but will be unable to find shortest paths in this problem as shortest paths no longer exist.<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I just finished a script which executes the Bellman-Ford Algorithm on a randomly generated directed graph (possibly with negative arcs). It can be accessed here. The Bellman Ford algorithm is another shortest path algorithm. Unlike Dijkstra&#8217;s algorithm, though, this algorithm can handle edges with negative weights and detect negative cycles in a graph. Negative cycles [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-41","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/41","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=41"}],"version-history":[{"count":0,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/41\/revisions"}],"wp:attachment":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=41"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=41"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=41"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}