{"id":3661,"date":"2016-05-17T09:20:12","date_gmt":"2016-05-17T08:20:12","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=3661"},"modified":"2022-12-03T22:59:06","modified_gmt":"2022-12-03T21:59:06","slug":"algorithme-de-ford-fulkerson","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/ford-fulkerson-algorithm\/","title":{"rendered":"Ford-Fulkerson algorithm"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"3661\" class=\"elementor elementor-3661\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6769b0a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6769b0a\" 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-c2a6b02\" data-id=\"c2a6b02\" 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-79437e6 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"79437e6\" 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-a160e7d\" data-id=\"a160e7d\" 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-e797bca elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"e797bca\" 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-88bdc4c\" data-id=\"88bdc4c\" 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-2a8b0f0 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"2a8b0f0\" 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:\/\/fr.wikipedia.org\/wiki\/Algorithme_de_Ford-Fulkerson\" 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-5594fae8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5594fae8\" 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-6d1a8922\" data-id=\"6d1a8922\" 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-2ef1fe0 elementor-widget elementor-widget-text-editor\" data-id=\"2ef1fe0\" 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\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_84 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\/ford-fulkerson-algorithm\/#Algorithme-de-Ford-Fulkerson\" >Ford-Fulkerson algorithm<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/ford-fulkerson-algorithm\/#Lalgorithme-de-Ford-Fulkerson-pas-a-pas\" >Step by step Ford-Fulkerson algorithm<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-de-Ford-Fulkerson\"><\/span>Ford-Fulkerson algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">The Ford-Fulkerson algorithm searches for an increasing path in the <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> residual. It saturates this path if it exists, otherwise it returns the <a href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/\">maximum flow<\/a>. More precisely, the algorithm establishes a minimal cut to verify the optimality criterion. Remember that the flow is less than or equal to the cut.<\/div>\n\n<p class=\"wp-block-paragraph\">In order to initialize the algorithm, it is possible to attribute any flow in the graph by following simple paths (from the source to the sink). In the following diagram, we have taken the path s-2-3-t for initialization.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-3765 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/flow2-300x103.png\" alt=\"ford-fulkerson algorithm maximum flow max flow problem minimum cut deviation graph increasing flow\" width=\"300\" height=\"103\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/flow2-300x103.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/flow2-1024x352.png 1024w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/flow2-768x264.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/flow2-1200x412.png 1200w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/flow2.png 1263w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/figure>\n<\/div>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">After construction of the residual graph, a path from s to t is chosen if there is one. Otherwise we have the maximum flow. In the first case, the new flow is calculated according to the increasing path chosen in the deviation graph: we add the flow of the increasing path to the existing flow if the corresponding arc in the original graph is in the same direction as that of the deviation graph, otherwise we subtract the flow. The algorithm stops when there is no longer an increasing path.<\/div>\n\n<p class=\"wp-block-paragraph\">It is possible to form a cut using the last gap graph. We apply a path from s, all the vertices that can be traversed are in the set S, the others in the set T. Indeed, the arcs saturated by the flow cut the graph into two subsets, and form the value of the cut.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-3770 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/cut3.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"497\" height=\"332\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/cut3.png 497w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/05\/cut3-300x200.png 300w\" sizes=\"(max-width: 497px) 100vw, 497px\" \/><\/figure>\n<\/div>\n\n<p class=\"wp-block-paragraph\">If you want to increase the flow by changing the value, you will need to increase the maximum flow that can pass through these arcs.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Lalgorithme-de-Ford-Fulkerson-pas-a-pas\"><\/span>Step by step Ford-Fulkerson algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6445 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford1.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"1009\" height=\"273\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford1.png 1009w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford1-300x81.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford1-768x208.png 768w\" sizes=\"(max-width: 1009px) 100vw, 1009px\" \/><\/figure>\n<\/div>\n\n<p class=\"wp-block-paragraph\">The initial flow is 0. Here the residual graph G<sub>f<\/sub> is a copy of graph G. We are looking for a path from s to t, for example s-2-5-t:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6446 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford2.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"1013\" height=\"238\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford2.png 1013w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford2-300x70.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford2-768x180.png 768w\" sizes=\"(max-width: 1013px) 100vw, 1013px\" \/><\/figure>\n<\/div>\n\n<p class=\"wp-block-paragraph\">The minimum value of the path is 8. We add this flow of 8 to the path in the graph G.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6447 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford3.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"963\" height=\"260\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford3.png 963w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford3-300x81.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford3-768x207.png 768w\" sizes=\"(max-width: 963px) 100vw, 963px\" \/><\/figure>\n<\/div>\n\n<p class=\"wp-block-paragraph\">As a reminder, the residual graph must show the inverse arcs (representing the flows). The residual graph of the new iteration is as follows:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6448 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford4.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"975\" height=\"283\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford4.png 975w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford4-300x87.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford4-768x223.png 768w\" sizes=\"(max-width: 975px) 100vw, 975px\" \/><\/figure>\n<\/div>\n\n<p class=\"wp-block-paragraph\">Here we choose the path s-2-3-5-t, with 2 for the blocking flow. When we choose an inverse arc (thus representing a flow) the new flow in the graph G is reduced as shown by this new graph G.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6449 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford5.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"980\" height=\"265\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford5.png 980w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford5-300x81.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford5-768x208.png 768w\" sizes=\"(max-width: 980px) 100vw, 980px\" \/><\/figure>\n<\/div>\n\n<p class=\"wp-block-paragraph\">Value of the flow = 10. Etc\u2026<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6450 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford6.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"975\" height=\"294\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford6.png 975w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford6-300x90.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford6-768x232.png 768w\" sizes=\"(max-width: 975px) 100vw, 975px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6451 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford7.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"954\" height=\"255\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford7.png 954w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford7-300x80.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford7-768x205.png 768w\" sizes=\"(max-width: 954px) 100vw, 954px\" \/><\/figure>\n<\/div>\n\n<p class=\"wp-block-paragraph\">Flow value = 16<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6452 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford8.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"959\" height=\"280\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford8.png 959w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford8-300x88.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford8-768x224.png 768w\" sizes=\"(max-width: 959px) 100vw, 959px\" \/><\/figure>\n<\/div>\n\n<p class=\"wp-block-paragraph\">Choice of reverse arc (3,2):<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6453 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford9.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"975\" height=\"264\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford9.png 975w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford9-300x81.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford9-768x208.png 768w\" sizes=\"(max-width: 975px) 100vw, 975px\" \/><\/figure>\n<\/div>\n\n<p class=\"wp-block-paragraph\">Flow value = 18.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6454 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford10.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"967\" height=\"314\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford10.png 967w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford10-300x97.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford10-768x249.png 768w\" sizes=\"(max-width: 967px) 100vw, 967px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6455 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford11.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"975\" height=\"267\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford11.png 975w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford11-300x82.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford11-768x210.png 768w\" sizes=\"(max-width: 975px) 100vw, 975px\" \/><\/figure>\n<\/div>\n\n<p class=\"wp-block-paragraph\">Flow value = 19.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6456 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford12.png\" alt=\"maximum flow max flow problem minimum cut gap graph increasing flow ford-fulkerson algorithm\" width=\"963\" height=\"314\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford12.png 963w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford12-300x98.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/ford12-768x250.png 768w\" sizes=\"(max-width: 963px) 100vw, 963px\" \/><\/figure>\n<\/div>\n\n<p class=\"wp-block-paragraph\">There is no longer a path from s to t, we have found a maximum flow for this graph G.<\/p>\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<\/div>","protected":false},"excerpt":{"rendered":"<p>Maximum flow problem Home page Wiki Ford-Fulkerson algorithm The Ford-Fulkerson algorithm searches for an increasing path in the residual graph. It saturates this path... <\/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-3661","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3661","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=3661"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3661\/revisions"}],"predecessor-version":[{"id":17928,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3661\/revisions\/17928"}],"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=3661"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}