<ulclass="metadata page-metadata"data-bi-name="page info"lang="en-us"dir="ltr">

Last update:

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="April 16, 202500:46:24 UTC">April 16, 2025</span>&emsp;

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date"title="September 10, 202506:18:21 UTC">September 10, 2025</span>&emsp;

<p>Bellman-Ford algorithm allows you to check whether there exists a cycle of negative weight in the graph, and if it does, find one of these cycles.</p>

<p>The details of the algorithm are described in the article on the<ahref="bellman_ford.html">Bellman-Ford</a> algorithm.

Here we'll describe only its application to this problem.</p>

<p>The standard implementation of Bellman-Ford looks for a negative cycle reachable from some starting vertex<spanclass="arithmatex">$v$</span> ; however, the algorithm can be modified to justlooking for any negative cycle in the graph.

<p>The standard implementation of Bellman-Ford looks for a negative cycle reachable from some starting vertex<spanclass="arithmatex">$v$</span> ; however, the algorithm can be modified to justlook for any negative cycle in the graph.

For this we need to put all the distance  <spanclass="arithmatex">$d[i]$</span>  to zero and not infinity — as if we are looking for the shortest path from all vertices simultaneously; the validity of the detection of a negative cycle is not affected.</p>

<p>Do<spanclass="arithmatex">$N$</span> iterations of Bellman-Ford algorithm. If there were no changes on the last iteration, there is no cycle of negative weight in the graph. Otherwise take a vertex the distance to which has changed, and go from it via its ancestors until a cycle is found. This cycle will be the desired cycle of negative weight.</p>

<h3id="implementation">Implementation<aclass="headerlink"href="#implementation"title="Permanent link">&para;</a></h3>

<ulclass="metadata page-metadata"data-bi-name="page info"lang="en-us"dir="ltr">

<spanclass="contributors-text">Contributors:</span>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/jakobkogler"title="jakobkogler"data-bi-name="contributorprofile"target="_blank">jakobkogler</a> (36.7%)</li><li><ahref="https://github.com/mukeshkharita"title="mukeshkharita"data-bi-name="contributorprofile"target="_blank">mukeshkharita</a> (35.78%)</li><li><ahref="https://github.com/tcNickolas"title="tcNickolas"data-bi-name="contributorprofile"target="_blank">tcNickolas</a> (7.34%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (5.5%)</li><li><ahref="https://github.com/likecs"title="likecs"data-bi-name="contributorprofile"target="_blank">likecs</a> (3.67%)</li><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (2.75%)</li><li><ahref="https://github.com/svaderia"title="svaderia"data-bi-name="contributorprofile"target="_blank">svaderia</a> (2.75%)</li><li><ahref="https://github.com/sunil-sangwan"title="sunil-sangwan"data-bi-name="contributorprofile"target="_blank">sunil-sangwan</a> (2.75%)</li><li><ahref="https://github.com/Harsh-Mathur-1503"title="Harsh-Mathur-1503"data-bi-name="contributorprofile"target="_blank">Harsh-Mathur-1503</a> (1.83%)</li><li><ahref="https://github.com/deepanshu-Raj"title="deepanshu-Raj"data-bi-name="contributorprofile"target="_blank">deepanshu-Raj</a> (0.92%)</li></ul>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/jakobkogler"title="jakobkogler"data-bi-name="contributorprofile"target="_blank">jakobkogler</a> (36.7%)</li><li><ahref="https://github.com/mukeshkharita"title="mukeshkharita"data-bi-name="contributorprofile"target="_blank">mukeshkharita</a> (35.78%)</li><li><ahref="https://github.com/tcNickolas"title="tcNickolas"data-bi-name="contributorprofile"target="_blank">tcNickolas</a> (7.34%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (5.5%)</li><li><ahref="https://github.com/likecs"title="likecs"data-bi-name="contributorprofile"target="_blank">likecs</a> (3.67%)</li><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (2.75%)</li><li><ahref="https://github.com/sunil-sangwan"title="sunil-sangwan"data-bi-name="contributorprofile"target="_blank">sunil-sangwan</a> (2.75%)</li><li><ahref="https://github.com/Harsh-Mathur-1503"title="Harsh-Mathur-1503"data-bi-name="contributorprofile"target="_blank">Harsh-Mathur-1503</a> (1.83%)</li><li><ahref="https://github.com/svaderia"title="svaderia"data-bi-name="contributorprofile"target="_blank">svaderia</a> (1.83%)</li><li><ahref="https://github.com/aleksmish"title="aleksmish"data-bi-name="contributorprofile"target="_blank">aleksmish</a> (0.92%)</li><li><ahref="https://github.com/deepanshu-Raj"title="deepanshu-Raj"data-bi-name="contributorprofile"target="_blank">deepanshu-Raj</a> (0.92%)</li></ul>