{"id":815,"date":"2016-01-29T13:57:55","date_gmt":"2016-01-29T12:57:55","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=815"},"modified":"2022-12-03T22:58:49","modified_gmt":"2022-12-03T21:58:49","slug":"algorithme-de-ford-bellman","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/ford-bellman-algorithm\/","title":{"rendered":"Ford-Bellman algorithm"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"815\" class=\"elementor elementor-815\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6cc05c0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6cc05c0\" 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-1d73e05\" data-id=\"1d73e05\" 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-c172cfe elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"c172cfe\" 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\/recherche-de-chemin-theorie-des-graphes\/\">\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\">Recherche de chemin<\/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-03641ef\" data-id=\"03641ef\" 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-3d782ca elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"3d782ca\" 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-ed8f689\" data-id=\"ed8f689\" 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-119063a elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"119063a\" 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_Bellman-Ford\" 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-16d0c0a7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"16d0c0a7\" 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-76b2be1e\" data-id=\"76b2be1e\" 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-3f5f1ccd elementor-widget elementor-widget-text-editor\" data-id=\"3f5f1ccd\" 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=\"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\/ford-bellman-algorithm\/#Algorithme-de-Ford-Bellman\" >Algorithme de Ford-Bellman<\/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\/ford-bellman-algorithm\/#Exemple\" >Exemple<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-de-Ford-Bellman\"><\/span>Algorithme de Ford-Bellman<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Le probl\u00e8me des plus courts chemins \u00e0 partir d&rsquo;une origine n&rsquo;a de solution que s&rsquo;il n&rsquo;existe pas de circuit absorbant atteignable. L&rsquo;algorithme de Ford-Bellman v\u00e9rifie qu&rsquo;il n&rsquo;existe pas de circuit absorbant atteignable \u00e0 partir de <strong>s<\/strong>. Si c&rsquo;est le cas, il retourne les plus courts chemins \u00e0 partir de <strong>s<\/strong>. L&rsquo;algorithme de Ford-Bellman est un <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithme<\/a> de <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/dynamic-programming\/\">programmation dynamique<\/a> gourmand qui calcule les chemins les plus courts de taille croissante. Il convient \u00e0 n&rsquo;importe quel <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graphe<\/a>.<\/p>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p><strong>Conditions<\/strong>.<\/p>\n<ul>\n<li>Cas g\u00e9n\u00e9ral<\/li>\n<\/ul>\n<\/div>\n\n<p>Au d\u00e9part, la distance est initialis\u00e9e \u00e0 0 pour l&rsquo;origine et \u00e0 \u0081l&rsquo;infini pour les autres sommets.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6309 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/ford1-300x130.png\" alt=\"plus court chemin algorithme de Ford-Bellman ford\" width=\"300\" height=\"130\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/ford1-300x130.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/ford1.png 713w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/figure>\n<\/div>\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;\">\n<p>On va examiner tous les arcs et am\u00e9liorer si possible la valeur des chemins. La nouvelle valeur pour chaque sommet est la distance minimale de tous les chemins de taille k-1 auxquels on rajoute les ar\u00eates entrant dans le sommet. Comme il peut y avoir des circuits, il faut recommencer.<\/p>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6310 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/ford2.png\" alt=\"plus court chemin algorithme de Ford-Bellman ford\" width=\"578\" height=\"243\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/ford2.png 578w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/ford2-300x126.png 300w\" sizes=\"(max-width: 578px) 100vw, 578px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6311\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/ford3.png\" alt=\"algorithme de Ford-Bellman plus court chemin\" width=\"345\" height=\"329\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/ford3.png 345w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/ford3-300x286.png 300w\" sizes=\"(max-width: 345px) 100vw, 345px\" \/><\/figure>\n<\/div>\n\n<p>Pour des raisons pratiques, la r\u00e9solution du l&rsquo;algorithme de Ford-Bellman ne retourne qu&rsquo;un vecteur. Ce qui correspond \u00e0 une colonne courante du tableau pr\u00e9sent\u00e9.<\/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;\">\n<p><strong>Optimalit\u00e9.<\/strong><\/p>\n<p>Le chemin le plus court de l&rsquo;origine \u00e0 lui-m\u00eame est de 0. Puis les chemins de taille 1 sont calcul\u00e9s de telle sorte que nous ne gardons que le <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/\">plus court chemin<\/a> de l&rsquo;origine \u00e0 tout autre sommet.<\/p>\n<p>l&rsquo;algorithme calcule les plus courts chemins des chemins de taille k (pour l&rsquo;it\u00e9ration k) \u00e0 partir des plus courts chemins des chemins de taille k-1, il est donc optimal quelle que soit l&rsquo;it\u00e9ration d&rsquo;arr\u00eat de l&rsquo;algorithme.<\/p>\n<p>S&rsquo;il n&rsquo;y a pas ce circuit absorbant, un plus court chemin est n\u00e9cessairement \u00e9l\u00e9mentaire. On est donc s\u00fbr qu&rsquo;un plus court chemin doit alors \u00eatre trouv\u00e9 en au plus n-1 \u00e9tapes de l\u2019it\u00e9ration. Si une valeur de D est am\u00e9lior\u00e9e, c\u2019est qu&rsquo;il y a un circuit absorbant.<\/p>\n<\/div>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre><strong>pour<\/strong> <strong>chaque<\/strong> sommet u du graphe\n   d[u, 0] = +\u221e\nd[s, 0] = 0\n<b>pour<\/b> k = 1 <b>jusqu'\u00e0<\/b> Nombre de sommets - 1 <b>faire<\/b>\n    <b>pour chaque<\/b> arc (u, v) du graphe <b>faire<\/b>\n        d[v, k] := min(d[v, k-1], d[u, k-1] + poids(u, v))\n    <strong>fin<\/strong>\n<strong>fin<\/strong>\nretourner d<\/pre>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Exemple<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Prenons pour exemple le graphe suivant :<\/p>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6487 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman1.png\" alt=\"plus court chemin algorithme de Ford-Bellman ford\" width=\"426\" height=\"194\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman1.png 426w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman1-300x137.png 300w\" sizes=\"(max-width: 426px) 100vw, 426px\" \/><\/figure>\n\n<p>Prenons le noeud 5 comme source, puis on initialise les autres distances \u00e0 l&rsquo;infini. Le vecteur\u00a0\u03c0 repr\u00e9sente les pr\u00e9d\u00e9cesseurs.<\/p>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6488 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman2.png\" alt=\"plus court chemin algorithme de Ford-Bellman ford\" width=\"684\" height=\"194\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman2.png 684w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman2-300x85.png 300w\" sizes=\"(max-width: 684px) 100vw, 684px\" \/><\/figure>\n\n<p><i>It\u00e9ration<\/i><em>\u00a01<\/em>: Les arcs (<em>u<\/em><sub>5<\/sub>,<em>u<\/em><sub>2<\/sub>) et (<em>u<\/em><sub>5<\/sub>,<em>u<\/em><sub>4<\/sub>) sont relax\u00e9s, on met \u00e0 jour les distances et les pr\u00e9d\u00e9cesseurs.<\/p>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6489 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman3.png\" alt=\"plus court chemin algorithme de Ford-Bellman ford\" width=\"684\" height=\"195\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman3.png 684w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman3-300x86.png 300w\" sizes=\"(max-width: 684px) 100vw, 684px\" \/><\/figure>\n\n<p><i>It\u00e9ration<\/i><em>\u00a02<\/em>: Les arcs (<em>u<\/em><sub>2<\/sub>,<em>u<\/em><sub>1<\/sub>), (<em>u<\/em><sub>4<\/sub>,<em>u<\/em><sub>2<\/sub>) et (<em>u<\/em><sub>4<\/sub>,<em>u<\/em><sub>3<\/sub>) sont relax\u00e9s, on met \u00e0 jour les distances aux noeuds 1, 2, et 4. Notons que (<em>u<\/em><sub>4<\/sub>,<em>u<\/em><sub>2<\/sub>) trouve un plus court chemin vers 2 en passant par le noeud 4.<\/p>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6490 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman4.png\" alt=\"plus court chemin algorithme de Ford-Bellman ford\" width=\"684\" height=\"194\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman4.png 684w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman4-300x85.png 300w\" sizes=\"(max-width: 684px) 100vw, 684px\" \/><\/figure>\n\n<p><i>It\u00e9ration<\/i><em>\u00a03<\/em>: Les arcs (<em>u<\/em><sub>2<\/sub>,<em>u<\/em><sub>1<\/sub>) sont relax\u00e9s (car on a trouv\u00e9 un chemin plus court pour aller au noeud 2 dans la derni\u00e8re it\u00e9ration).<\/p>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6491 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman5.png\" alt=\"plus court chemin algorithme de Ford-Bellman ford\" width=\"684\" height=\"194\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman5.png 684w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman5-300x85.png 300w\" sizes=\"(max-width: 684px) 100vw, 684px\" \/><\/figure>\n\n<p><i>It\u00e9ration<\/i><em>\u00a04<\/em>: Aucun arc n&rsquo;est relax\u00e9.<\/p>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6492 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman6.png\" alt=\"plus court chemin algorithme de Ford-Bellman ford\" width=\"684\" height=\"194\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman6.png 684w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman6-300x85.png 300w\" sizes=\"(max-width: 684px) 100vw, 684px\" \/><\/figure>\n\n<p>Les chemins les plus courts partant du noeud 5 sont :<\/p>\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6493 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman7.png\" alt=\"plus court chemin algorithme de Ford-Bellman ford\" width=\"587\" height=\"195\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman7.png 587w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/07\/bellman7-300x100.png 300w\" sizes=\"(max-width: 587px) 100vw, 587px\" \/><\/figure>\n\n<p>L&rsquo;algorithme se pr\u00e9sente sous la forme d&rsquo;un tableau comme ci-dessous :<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>Iteration<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<td>4<\/td>\n<td>5<\/td>\n<\/tr>\n<tr>\n<td>0<\/td>\n<td>inf<\/td>\n<td>inf<\/td>\n<td>inf<\/td>\n<td>inf<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>inf<\/td>\n<td><span style=\"color: #993300;\">4(5)<\/span><\/td>\n<td>inf<\/td>\n<td><span style=\"color: #993300;\">2(5)<\/span><\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>2<\/td>\n<td><span style=\"color: #993300;\">7(2)<\/span><\/td>\n<td><span style=\"color: #993300;\">3(4)<\/span><\/td>\n<td><span style=\"color: #993300;\">3(4)<\/span><\/td>\n<td>2(5)<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>3<\/td>\n<td><span style=\"color: #993300;\">6(2)<\/span><\/td>\n<td>3(4)<\/td>\n<td>3(4)<\/td>\n<td>2(5)<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>4<\/td>\n<td>6(2)<\/td>\n<td>3(4)<\/td>\n<td>3(4)<\/td>\n<td>2(5)<\/td>\n<td>0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>Les distances en rouge montre les noeuds qui ont subi un changement dans l&rsquo;it\u00e9ration courante. Pour l&rsquo;it\u00e9ration suivante il faut donc relax\u00e9 les arcs provenant de ces noeuds. L&rsquo;algorithme s&rsquo;arr\u00eate lorsqu&rsquo;il n&rsquo;y a plus de changement.<\/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>Path Finding Wiki Home Page Ford-Bellman Algorithm The problem of shortest paths from an origin has a solution only if there is no \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-815","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/815","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=815"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/815\/revisions"}],"predecessor-version":[{"id":18359,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/815\/revisions\/18359"}],"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=815"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}