{"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\/en\/graph-theory-path-search\/floyd-warshall-transitive-closure-algorithm\/","title":{"rendered":"Floyd Warshall algorithm (transitive closure)"},"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\/en\/graph-theory-path-search\/\">\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\">Path search<\/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\/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-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\">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\/graph-theory-path-search\/floyd-warshall-transitive-closure-algorithm\/#Algorithme-de-Floyd-Warshall\" >Floyd Warshall 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\/graph-theory-path-search\/floyd-warshall-transitive-closure-algorithm\/#Exemple-de-lalgorithme-de-Floyd-Warshall\" >Example of the Floyd Warshall algorithm<\/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\/en\/graph-theory-path-search\/floyd-warshall-transitive-closure-algorithm\/#Optimalite-de-lalgorithme-de-Floyd-Warshall\" >Optimality of the Floyd Warshall algorithm<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-de-Floyd-Warshall\"><\/span>Floyd Warshall algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2><p>We want to determine the shortest paths between all pairs of vertices. We could use <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/algorithm-of-dijkstra\/\">Dijkstra<\/a> of <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/ford-bellman-algorithm\/\">Bellman Ford<\/a>, with each vertex as source. Can we do better? In Floyd Warshall&#039;s algorithm, we assume that we have access to a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> with n vertices as n\u00b2 adjacency matrix.<\/p><p>Floyd Warshall&#039;s algorithm takes as input a directed and valued graph, described by an adjacency matrix giving the weight of an arc when it exists and the value \u221e otherwise. The weight of a path between two vertices is the sum of the weights on the arcs constituting this path. The arcs of the graph can have negative weights, but the graph must not have a circuit of strictly negative weight. The algorithm calculates, for each pair of vertices, the minimum weight among all the paths between these two vertices.<\/p><div><p><strong>Conditions<\/strong>.<\/p><ul><li>Extended general case<\/li><\/ul><\/div><p>We suppose that the vertices of G are {1, 2, 3, 4, ..., <i>not<\/i>}. It successively solves the following sub-problems:<\/p><div><p>W<sup>k<\/sup><sub>ij<\/sub> is the minimum weight of a path from vertex i to vertex <i>j<\/i> borrowing only intermediate vertices in {1, 2, 3,\u2026, <i>k<\/i>} if there is one, and \u221e otherwise. We denote by W<sup>k<\/sup> the matrix of W<sup>k<\/sup><sub>ij.<\/sub><\/p><\/div><div><p>For k = 0, W<sup>0<\/sup> is the adjacency matrix defining the graph.<\/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=\"shortest path floyd-warshall algorithm transitive closure\" 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>To find a recurrence relation, we consider a path <i>p<\/i> Between <i>i<\/i> and <i>j<\/i> of minimal weight whose intermediate vertices are in {1, 2, 3, ..., <i>k<\/i>} :<\/p><ul><li>that is <i>p<\/i> do not take the summit <i>k<\/i><\/li><li>that is <i>p<\/i> borrows exactly once the summit <i>k<\/i> and <i>p<\/i> is therefore the concatenation of two paths, between <i>i<\/i> and <i>k<\/i> and <i>k<\/i> and <i>j<\/i> respectively, whose intermediate vertices are in {1, 2, 3,\u2026, <i>k<\/i>-1}.<\/li><\/ul><\/div><p>Let p be the shortest path from i to j with all the intermediate vertices of the set {1 ,. . . , k}. If k is not an intermediate vertex of p, then p is also a shortest path with all the intermediate vertices of the set {1 ,. . . , k - 1}. If k is an intermediate vertex of p, we decompose p into a path p1 between i and k, and a path p2 between k and j; these are the shortest paths.<\/p><p>The above observation gives the recurrence relation:<\/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> ), for everyone <i>i<\/i>, <i>j<\/i> and <i>k<\/i> in {1, 2, 3, 4\u2026, <i>not<\/i>}.<\/p><\/div><p>Thus we solve the subproblems by increasing value of 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=\"shortest path floyd-warshall algorithm transitive closure\" 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=\"shortest path floyd-warshall algorithm transitive closure\" 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>Which gives on the first two stages:<\/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=\"shortest path floyd-warshall algorithm transitive closure\" 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=\"shortest path floyd-warshall algorithm transitive closure\" 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=\"shortest path floyd-warshall algorithm transitive closure\" width=\"247\" height=\"120\" title=\"\"><\/figure><h2><span class=\"ez-toc-section\" id=\"Exemple-de-lalgorithme-de-Floyd-Warshall\"><\/span>Example of the Floyd Warshall algorithm<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=\"shortest path floyd-warshall algorithm transitive closure\" 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>The first matrix is the adjacent matrix then the shortest paths. The second matrix presents the predecessors. It is initialized by a value z which is equal to the number of the row if a value exists in the adjacency matrix (in the initial state). The matrix of predecessors is updated each time a value in (i, j) is modified. The corresponding value in (i, j) of the matrix of the predecessors is equal to the number of iterations (that is to say the value of the power of the matrix).<\/p><h2><span class=\"ez-toc-section\" id=\"Optimalite-de-lalgorithme-de-Floyd-Warshall\"><\/span>Optimality of the Floyd Warshall algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2><div><p>Initially, we have the shortest size 1 trails starting from all peaks. Next, we compute the larger-sized paths through vertex 1, and we keep only the shortest paths. The new iteration therefore displays the shortest paths of size 1 and those of size 2 passing through the vertex 1. By induction, we deduce that the last matrix displays the shortest paths of size less than the number of vertices between any pair of vertices .<\/p><\/div><div><pre>CODE W is the adjacency matrix\n<b>for <\/b>k from 1 to n\n<b>   for <\/b>i from 1 to n\n<b>      for <\/b>j from 1 to n 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>end<\/strong>\n   <strong>end<\/strong>\n<strong>end<\/strong>\nreturn 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 Floyd Warshall&#039;s Algorithm We want to find the shortest paths between all pairs of vertices. We \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\/en\/wp-json\/wp\/v2\/pages\/848","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=848"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/848\/revisions"}],"predecessor-version":[{"id":17926,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/848\/revisions\/17926"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/362"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=848"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}