{"id":848,"date":"2016-01-29T14:46:39","date_gmt":"2016-01-29T13:46:39","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=848"},"modified":"2022-12-03T22:58:49","modified_gmt":"2022-12-03T21:58:49","slug":"algoritme-de-floyd-warshall-fermeture-transitive","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-cierre-transitivo-floyd-warshall\/","title":{"rendered":"Algoritmo de Floyd Warshall (cierre transitivo)"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"848\" class=\"elementor elementor-848\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e48860a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e48860a\" 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-bebae54\" data-id=\"bebae54\" 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-5b00ce8 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5b00ce8\" 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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/\">\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\">B\u00fasqueda de ruta<\/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-a1a724a\" data-id=\"a1a724a\" 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-1c30ee9 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"1c30ee9\" 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\/es\/\">\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\">Pagina de inicio<\/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-05bb898\" data-id=\"05bb898\" 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-f8bc326 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f8bc326\" 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_Floyd-Warshall\" 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-e9a192a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e9a192a\" 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-7f0ea4f\" data-id=\"7f0ea4f\" 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-430f13f elementor-widget elementor-widget-text-editor\" data-id=\"430f13f\" 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<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\">Contenido<\/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=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/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\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-cierre-transitivo-floyd-warshall\/#Algorithme-de-Floyd-Warshall\" >Algoritmo de Floyd Warshall<\/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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-cierre-transitivo-floyd-warshall\/#Exemple-de-lalgorithme-de-Floyd-Warshall\" >Ejemplo del algoritmo de Floyd Warshall<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-cierre-transitivo-floyd-warshall\/#Optimalite-de-lalgorithme-de-Floyd-Warshall\" >Optimidad del algoritmo Floyd Warshall<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-de-Floyd-Warshall\"><\/span>Algoritmo de Floyd Warshall<span class=\"ez-toc-section-end\"><\/span><\/h2><p>Queremos determinar los caminos m\u00e1s cortos entre todos los pares de v\u00e9rtices. Podr\u00edamos usar <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-dijkstra\/\">Dijkstra<\/a> de <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-ford-bellman-2\/\">botones vado<\/a>, con cada v\u00e9rtice como fuente. \u00bfPodemos hacerlo mejor? En el algoritmo de Floyd Warshall, asumimos que tenemos acceso a un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a> con n v\u00e9rtices como matriz de adyacencia n\u00b2.<\/p><p>El algoritmo de Floyd Warshall toma como entrada un gr\u00e1fico dirigido y valorado, descrito por una matriz de adyacencia que da el peso de un arco cuando existe y el valor \u221e en caso contrario. El peso de un camino entre dos v\u00e9rtices es la suma de los pesos en los arcos que constituyen este camino. Los arcos del gr\u00e1fico pueden tener pesos negativos, pero el gr\u00e1fico no debe tener un circuito de peso estrictamente negativo. El algoritmo calcula, para cada par de v\u00e9rtices, el peso m\u00ednimo entre todos los caminos entre estos dos v\u00e9rtices.<\/p><div><p><strong>Condiciones<\/strong>.<\/p><ul><li>Caso general extendido<\/li><\/ul><\/div><p>Suponemos que los v\u00e9rtices de G son {1, 2, 3, 4, ..., <i>no<\/i>}. Resuelve sucesivamente los siguientes subproblemas:<\/p><div><p>W<sup>k<\/sup><sub>ij<\/sub> es el peso m\u00ednimo de un camino desde el v\u00e9rtice i al v\u00e9rtice <i>j<\/i> tomando prestados solo v\u00e9rtices intermedios en {1, 2, 3,\u2026, <i>k<\/i>} si hay uno, y \u221e en caso contrario. Denotamos por W<sup>k<\/sup> la matriz de W<sup>k<\/sup><sub>ij.<\/sub><\/p><\/div><div><p>Para k = 0, W<sup>0<\/sup> es la matriz de adyacencia que define el gr\u00e1fico.<\/p><figure><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6316 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/fw1.png\" alt=\"cierre transitivo del algoritmo de floyd-warshall del camino m\u00e1s corto\" width=\"449\" height=\"141\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/fw1.png 449w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/fw1-300x94.png 300w\" sizes=\"(max-width: 449px) 100vw, 449px\" \/><\/figure><p>Para encontrar una relaci\u00f3n de recurrencia, consideramos un camino <i>pag<\/i> Entre <i>I<\/i> y <i>j<\/i> de peso m\u00ednimo cuyos v\u00e9rtices intermedios est\u00e1n en {1, 2, 3,\u2026, <i>k<\/i>} :<\/p><ul><li>es decir <i>pag<\/i> no tomes la cumbre <i>k<\/i><\/li><li>es decir <i>pag<\/i> toma prestado exactamente una vez que la cumbre <i>k<\/i> y <i>pag<\/i> es, por tanto, la concatenaci\u00f3n de dos caminos, entre <i>I<\/i> y <i>k<\/i> y <i>k<\/i> y <i>j<\/i> respectivamente, cuyos v\u00e9rtices intermedios est\u00e1n en {1, 2, 3,\u2026, <i>k<\/i>-1}.<\/li><\/ul><\/div><p>Sea p el camino m\u00e1s corto de i a j con todos los v\u00e9rtices intermedios del conjunto {1,. . . , k}. Si k no es un v\u00e9rtice intermedio de p, entonces p tambi\u00e9n es un camino m\u00e1s corto con todos los v\u00e9rtices intermedios del conjunto {1,. . . , k - 1}. Si k es un v\u00e9rtice intermedio de p, descomponemos p en un camino p1 entre i y k, y un camino p2 entre k y j; estos son los caminos m\u00e1s cortos.<\/p><p>La observaci\u00f3n anterior da la relaci\u00f3n de recurrencia:<\/p><div><p>W<sup>k<\/sup><sub>ij<\/sub>= min (W<sup>k-1<\/sup><sub>ij<\/sub>, W<sup>k-1<\/sup><sub>ik<\/sub> + W<sup>k-1<\/sup><sub>K J<\/sub> ), para todos <i>I<\/i>, <i>j<\/i> y <i>k<\/i> en {1, 2, 3, 4\u2026, <i>no<\/i>}.<\/p><\/div><p>Por tanto, resolvemos los subproblemas aumentando el valor de k.<\/p><figure><img decoding=\"async\" class=\"alignnone wp-image-6482 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/warshall1.png\" alt=\"cierre transitivo del algoritmo de floyd-warshall del camino m\u00e1s corto\" width=\"700\" height=\"245\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/warshall1.png 700w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/warshall1-300x105.png 300w\" sizes=\"(max-width: 700px) 100vw, 700px\" \/><\/figure><figure><img decoding=\"async\" class=\"alignnone wp-image-6483 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/warshall2.png\" alt=\"cierre transitivo del algoritmo de floyd-warshall del camino m\u00e1s corto\" width=\"332\" height=\"217\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/warshall2.png 332w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/warshall2-300x196.png 300w\" sizes=\"(max-width: 332px) 100vw, 332px\" \/><\/figure><p>Lo que da en las dos primeras etapas:<\/p><figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6484 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/warshall3.png\" alt=\"cierre transitivo del algoritmo de floyd-warshall del camino m\u00e1s corto\" width=\"377\" height=\"110\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/warshall3.png 377w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/warshall3-300x88.png 300w\" sizes=\"(max-width: 377px) 100vw, 377px\" \/><\/figure><figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6485 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/warshall4.png\" alt=\"cierre transitivo del algoritmo de floyd-warshall del camino m\u00e1s corto\" width=\"247\" height=\"120\" title=\"\"><\/figure><figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6486 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/warshall5.png\" alt=\"cierre transitivo del algoritmo de floyd-warshall del camino m\u00e1s corto\" width=\"247\" height=\"120\" title=\"\"><\/figure><h2><span class=\"ez-toc-section\" id=\"Exemple-de-lalgorithme-de-Floyd-Warshall\"><\/span>Ejemplo del algoritmo de Floyd Warshall<span class=\"ez-toc-section-end\"><\/span><\/h2><div><figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-855 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/dujap.jpg\" alt=\"cierre transitivo del algoritmo de floyd-warshall del camino m\u00e1s corto\" width=\"613\" height=\"806\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/dujap.jpg 613w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/dujap-228x300.jpg 228w\" sizes=\"(max-width: 613px) 100vw, 613px\" \/><\/figure><\/div><p>La primera matriz es la matriz adyacente y luego los caminos m\u00e1s cortos. La segunda matriz presenta a los predecesores. Se inicializa con un valor z que es igual al n\u00famero de la fila si existe un valor en la matriz de adyacencia (en el estado inicial). La matriz de predecesores se actualiza cada vez que se modifica un valor en (i, j). El valor correspondiente en (i, j) de la matriz de los predecesores es igual al n\u00famero de iteraciones (es decir, el valor de la potencia de la matriz).<\/p><h2><span class=\"ez-toc-section\" id=\"Optimalite-de-lalgorithme-de-Floyd-Warshall\"><\/span>Optimidad del algoritmo Floyd Warshall<span class=\"ez-toc-section-end\"><\/span><\/h2><div><p>Inicialmente, tenemos los senderos de tama\u00f1o 1 m\u00e1s cortos que comienzan desde todos los picos. A continuaci\u00f3n, calculamos las rutas de mayor tama\u00f1o a trav\u00e9s del v\u00e9rtice 1 y mantenemos solo las rutas m\u00e1s cortas. Por lo tanto, la nueva iteraci\u00f3n muestra las rutas m\u00e1s cortas de tama\u00f1o 1 y las de tama\u00f1o 2 que pasan por el v\u00e9rtice 1. Por inducci\u00f3n, deducimos que la \u00faltima matriz muestra las rutas m\u00e1s cortas de tama\u00f1o menor que el n\u00famero de v\u00e9rtices entre cualquier par de v\u00e9rtices.<\/p><\/div><div><pre>CODE W es la matriz de adyacencia\n<b>para <\/b>k de 1 an\n<b>   para <\/b>yo de 1 a n\n<b>      para <\/b>j de 1 an W<sup>k<\/sup><sub>ij<\/sub>= min (W<sup>k-1<\/sup><sub>ij<\/sub>, W<sup>k-1<\/sup><sub>ik<\/sub> + W<sup>k-1<\/sup><sub>K J<\/sub> )\n      <strong>fin<\/strong>\n   <strong>fin<\/strong>\n<strong>fin<\/strong>\nvolver W<\/pre><\/div>\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-40bbce7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"40bbce7\" 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-6eaad8b\" data-id=\"6eaad8b\" 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\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>Path Finding Home Wiki Algoritmo de Floyd Warshall Queremos encontrar los caminos m\u00e1s cortos entre todos los pares de v\u00e9rtices. Nosotros \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":362,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-848","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/848","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=848"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/848\/revisions"}],"predecessor-version":[{"id":17926,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/848\/revisions\/17926"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/362"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=848"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}