{"id":4428,"date":"2016-08-24T10:08:15","date_gmt":"2016-08-24T09:08:15","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=4428"},"modified":"2022-12-03T23:00:11","modified_gmt":"2022-12-03T22:00:11","slug":"cycle-canceling-algorithm","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/cycle-canceling-algorithm\/","title":{"rendered":"Cycle-canceling algorithm"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"4428\" class=\"elementor elementor-4428\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ee37c1c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ee37c1c\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-7521c7b\" data-id=\"7521c7b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a4f9db9 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a4f9db9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Maximum flow problem<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-1a5a1e3\" data-id=\"1a5a1e3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a91a301 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a91a301\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-7488800\" data-id=\"7488800\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-470f2b6 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"470f2b6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/algorithms.discrete.ma.tum.de\/\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4de2eaa0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4de2eaa0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4bcef52\" data-id=\"4bcef52\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5de0be8f elementor-widget elementor-widget-text-editor\" data-id=\"5de0be8f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/cycle-canceling-algorithm\/#Cycle-canceling-algorithme\" >Cycle-canceling algorithm<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Cycle-canceling-algorithme\"><\/span>Cycle-canceling algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The cycle-canceling <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> begins with a resolution of <a href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/\">maximum flow<\/a>. Then, iteratively, the algorithm searches for a cycle with a negative cost (negative cost if the edge is taken in the opposite direction to the flow) and increases the flow on this cycle. When there are no more negative cycles, the algorithm ends.<\/p>\n<p><\/p>\n<p>Example :<\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-4472 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca1.png\" alt=\"cycle-canceling negative cycle algorithm\" width=\"711\" height=\"368\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca1.png 711w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca1-300x155.png 300w\" sizes=\"(max-width: 711px) 100vw, 711px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p>let&#039;s build it <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> gap and look for a negative cycle:<\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4477 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca2.png\" alt=\"cycle-canceling negative cycle algorithm\" width=\"772\" height=\"345\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca2.png 772w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca2-300x134.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/cca2-768x343.png 768w\" sizes=\"(max-width: 772px) 100vw, 772px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p>The 4-2-3-4 cycle has a cost of -3 + 1 + 1 = -1, we can saturate it with a flow of 2.<\/p>\n<p><\/p>\n<p>Similarly with the 4-2-1-3-4 cycle with a cost of -3 -2 +2 +1 = -2, we can saturate it with a flow of 1.<\/p>\n<p><\/p>\n<p>There is no longer a negative cycle, the algorithm ends.<\/p>\n<p><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Maximum flow problem Home page Wiki Cycle-canceling algorithm The cycle-canceling algorithm starts with a maximum flow resolution. Then, iteratively, the algorithm seeks... <\/p>","protected":false},"author":1,"featured_media":0,"parent":3587,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-4428","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4428","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=4428"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4428\/revisions"}],"predecessor-version":[{"id":18462,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4428\/revisions\/18462"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3587"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=4428"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}