{"id":3844,"date":"2016-05-17T12:19:35","date_gmt":"2016-05-17T11:19:35","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=3844"},"modified":"2022-12-03T22:59:06","modified_gmt":"2022-12-03T21:59:06","slug":"algorithme-dedmonds-karp","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/algoritmo-dedmonds-karp\/","title":{"rendered":"Algoritmo de Edmonds-Karp"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"3844\" class=\"elementor elementor-3844\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-194026f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"194026f\" 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-99bc845\" data-id=\"99bc845\" 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-93a2b91 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"93a2b91\" 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\/probleme-de-flot-maximum\/\">\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\">Probl\u00e8me de flot maximum<\/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-3248094\" data-id=\"3248094\" 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-9b52536 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"9b52536\" 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\/\">\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\">Page d'accueil<\/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-fd3a2c3\" data-id=\"fd3a2c3\" 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-942cf2f elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"942cf2f\" 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_d%27Edmonds-Karp\" 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-20975810 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"20975810\" 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-725da8ea\" data-id=\"725da8ea\" 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-3ee1a2f9 elementor-widget elementor-widget-text-editor\" data-id=\"3ee1a2f9\" 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_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\">Contenus<\/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=\"Alternar tabla de contenidos\"><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\/es\/problema-de-flujo-maximo\/algoritmo-dedmonds-karp\/#Algorithme-dEdmonds-Karp\" >Algorithme d&rsquo;Edmonds-Karp<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-dEdmonds-Karp\"><\/span>Algorithme d&rsquo;Edmonds-Karp<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>L&rsquo;algorithme d&rsquo;Edmonds-Karp \u00e0 un temps d\u2019ex\u00e9cution de O(VE\u00b2), il est plus rapide que l&rsquo;algorithme de <a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/ford-fulkerson-algoritmo-2\/\">Ford-Fulkerson<\/a> pour les graphes denses, c&rsquo;est \u00e0 dire un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">graphe<\/a> contenant un grand nombre d&rsquo;ar\u00eate (ou arcs) en fonction du nombre de sommets.<\/p>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">L&rsquo;algorithme d&rsquo;Edmonds-Karp est identique \u00e0 l&rsquo;algorithme de Ford-Fulkerson, \u00e0 l&rsquo;exception de l&rsquo;ordre de recherche utilis\u00e9 pour d\u00e9terminer un chemin augmentant. Le chemin trouv\u00e9 doit \u00eatre le chemin le plus court qui poss\u00e8de une capacit\u00e9 positive. Un tel chemin peut \u00eatre trouv\u00e9 par un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/recorrido-de-grafos\/\">parcours en largeur<\/a>, en supposant que les arcs ont tous une longueur unit\u00e9. On note que la longueur du chemin augmentant cro\u00eet \u00e0 chaque it\u00e9ration.<\/div>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre><b><em>Code provenant de wikip\u00e9dia<\/em>\nalgorithm<\/b> EdmondsKarp\n    <b>input<\/b>:\n        C[1..n, 1..n] <i>(matrice des capacit\u00e9s)<\/i>\n        E[1..n, 1..?] <i>(listes des voisins)<\/i>\n        s             <i>(source)<\/i>\n        t             <i>(puits)<\/i>\n    <b>output<\/b>:\n        f             <i>(valeur du flot maximum)<\/i>\n        F             <i>(matrice donnant un flot valide de valeur maximum)<\/i>\n    f := 0 <i>(le flot initial est nul)<\/i>\n    F := <b>array<\/b>(1..n, 1..n) <i>(la <a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/\">capacit\u00e9 r\u00e9siduelle<\/a> de u \u00e0 v est C[u,v] - F[u,v])<\/i>\n    <b>forever<\/b>\n        m, P := BreadthFirstSearch(C, E, s, t, F)\n        <b>if<\/b> m = 0\n            <b>break<\/b>\n        f := f + m\n        <i>(Backtrack et noter le flot)<\/i>\n        v := t\n        <b>while<\/b> v \u2260 s\n            u := P[v]\n            F[u,v] := F[u,v] + m\n            F[v,u] := F[v,u] - m\n            v := u\n    <b>return<\/b> (f, F)\n<\/pre>\n<\/div>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre><b>algorithm<\/b> BreadthFirstSearch\n    <b>input<\/b>:\n        C, E, s, t, F\n    <b>output<\/b>:\n        M[t]          <i>(capacit\u00e9 du chemin trouv\u00e9)<\/i>\n        P             <i>(table des parents)<\/i>\n    P := <b>array<\/b>(1..n)\n    <b>for<\/b> u <b>in<\/b> 1..n\n        P[u] := -1\n    P[s] := -2 <i>(pour assurer que la source n'est pas red\u00e9couverte)<\/i> \n    M := <b>array<\/b>(1..n) <i>(capacit\u00e9 du chemin trouv\u00e9 jusqu'au n\u0153ud)<\/i>\n    M[s] := \u221e\n    Q := queue()\n    Q.push(s)\n    <b>while<\/b> Q.size() &gt; 0\n        u := Q.pop()\n        <b>for<\/b> v <b>in<\/b> E[u]\n            <b>if<\/b> C[u,v] - F[u,v] &gt; 0 <b>and<\/b> P[v] = -1\n                P[v] := u\n                M[v] := min(M[u], C[u,v] - F[u,v])\n                <b>if<\/b> v \u2260 t\n                    Q.push(v)\n                <b>else<\/b>\n                    <b>return<\/b> M[t], P\n    <b>return<\/b> 0, P<\/pre>\n<\/div>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-9856 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/ek.jpg\" alt=\"algorithme d&#039;edmonds-karp flot maximum max flow problem coupe minimale graphe d&#039;\u00e9cart flot augmentant\" width=\"321\" height=\"674\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/ek.jpg 321w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/ek-143x300.jpg 143w\" sizes=\"(max-width: 321px) 100vw, 321px\" \/><\/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>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Problema de flujo m\u00e1ximo P\u00e1gina de inicio Wiki Algoritmo de Edmonds-Karp El algoritmo de Edmonds-Karp tiene un tiempo de ejecuci\u00f3n de O(VE\u00b2), es m\u00e1s r\u00e1pido que el algoritmo de Ford-Fulkerson... <\/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-3844","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3844","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=3844"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3844\/revisions"}],"predecessor-version":[{"id":17929,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3844\/revisions\/17929"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3587"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=3844"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}