{"id":362,"date":"2016-01-26T16:30:19","date_gmt":"2016-01-26T15:30:19","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=362"},"modified":"2024-02-11T19:52:24","modified_gmt":"2024-02-11T18:52:24","slug":"recherche-de-chemin-theorie-des-graphes","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/","title":{"rendered":"Pathfinding 101"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"362\" class=\"elementor elementor-362\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c39f8aa elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c39f8aa\" 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-e9bd86a\" data-id=\"e9bd86a\" 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-10edd0b elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"10edd0b\" 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\/2020\/04\/03\/theories-and-algorithms-2\/\">\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\">Theories<\/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-5acdfa9\" data-id=\"5acdfa9\" 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-846d48f elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"846d48f\" 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-b552b0d\" data-id=\"b552b0d\" 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-5712c05 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5712c05\" 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=\"\">\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-f437607 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f437607\" 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-65bbee3\" data-id=\"65bbee3\" 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-370c6b8 elementor-widget elementor-widget-toggle\" data-id=\"370c6b8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5771\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5771\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">I. Shortest path, single source (path search)<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5771\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5771\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> undirected\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/algorithm-of-dijkstra\/\">Dijkstra&#039;s algorithm<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/johnson-algorithm\/\">Dijkstra with binary heap<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Fibonacci_heap\" target=\"_blank\" rel=\"noopener\">Dijkstra with Fibonacci heap<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Thorup<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Directed graph with non-negative weights\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/bellman-algorithm\/\">Bellman&#039;s algorithm<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/ford-bellman-algorithm\/\">Ford-Bellman algorithm<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/simplex-method-2\/\">Danzig algorithm<\/a><\/li>\n<li><a href=\"https:\/\/link.springer.com\/article\/10.1007\/BF01386390?error=cookies_not_supported&#038;code=43bcb593-58ff-408e-9ca3-59cadf5ea764\" target=\"_blank\" rel=\"noopener\">Dijkstra with list<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/johnson-algorithm\/\">Dijkstra with binary heap<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Fibonacci_heap\" target=\"_blank\" rel=\"noopener\">Dijkstra with Fibonacci heap<\/a><\/li>\n<li><a href=\"https:\/\/link.springer.com\/article\/10.1007\/BF01786986?error=cookies_not_supported&#038;code=51bb4a86-7420-4e9f-bae3-e6233ac3061d\" target=\"_blank\" rel=\"noopener\">Johnson<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Gabow%27s_algorithm\" target=\"_blank\" rel=\"noopener\">Gabow<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/doi\/10.1145\/77600.77615?cookieSet=1\" target=\"_blank\" rel=\"noopener\">Ahuja et al.<\/a><\/li>\n<li><a href=\"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S002200000400042X\" target=\"_blank\" rel=\"noopener\">Thorup<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Directed graph with all types of weights\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/ford-bellman-algorithm\/\">Ford-Bellman algorithm<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Based on a heuristic\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/star-algorithm\/\">Algorithm A *<\/a><\/li>\n<li><a href=\"http:\/\/robots.stanford.edu\/papers\/Likhachev03b.pdf\" target=\"_blank\" rel=\"noopener\">Anytime Repairing A * (ARA *)<\/a><\/li>\n<li><a href=\"http:\/\/www.cs.cmu.edu\/~ggordon\/likhachev-etal.anytime-dstar.pdf\" target=\"_blank\" rel=\"noopener\">Anytime Dynamic A *<\/a><\/li>\n<li><a href=\"https:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.15.3683\" target=\"_blank\" rel=\"noopener\">D *<\/a><\/li>\n<li><a href=\"https:\/\/web.archive.org\/web\/20090219220415\/http:\/\/www.cs.ualberta.ca\/~games\/pathfind\/publications\/cig2005.pdf\" target=\"_blank\" rel=\"noopener\">Fringe<\/a><\/li>\n<li><a href=\"https:\/\/www.ijcai.org\/Proceedings\/07\/Papers\/385.pdf\" target=\"_blank\" rel=\"noopener\">Fringe Saving A * (FSA *)<\/a><\/li>\n<li><a href=\"https:\/\/www.researchgate.net\/publication\/221455192_Generalized_Adaptive_A\" target=\"_blank\" rel=\"noopener\">Generalized Adaptive A * (GAA *)<\/a><\/li>\n<li><a href=\"https:\/\/www.researchgate.net\/publication\/220605574_Incremental_Heuristic_Search_in_AI\" target=\"_blank\" rel=\"noopener\">Incremental heuristic search<\/a><\/li>\n<li><a href=\"http:\/\/www.eng.tau.ac.il\/~bengal\/GTA.pdf\" target=\"_blank\" rel=\"noopener\">Informational search<\/a><\/li>\n<li><a href=\"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0004370285900840\" target=\"_blank\" rel=\"noopener\">Iterative deepening A * (IDA *)<\/a><\/li>\n<li><a href=\"https:\/\/www.aaai.org\/ocs\/index.php\/SOCS\/SOCS12\/paper\/viewFile\/5396\/5212\" target=\"_blank\" rel=\"noopener\">Jump point search<\/a><\/li>\n<li><a href=\"https:\/\/www.aaai.org\/ocs\/index.php\/SOCS\/SOCS12\/paper\/viewFile\/5396\/5212\" target=\"_blank\" rel=\"noopener\">Lifelong Planning A * (LPA *)<\/a><\/li>\n<li><a href=\"https:\/\/ieeexplore.ieee.org\/document\/8994527\" target=\"_blank\" rel=\"noopener\">Multiplier-accelerated A * (MAA *)<\/a><\/li>\n<li><a href=\"https:\/\/repub.eur.nl\/pub\/16100\/ei2009-10.pdf\" target=\"_blank\" rel=\"noopener\">New Bidirectional A * (NBA *)<\/a><\/li>\n<li><a href=\"https:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.105.7839\" target=\"_blank\" rel=\"noopener\">Simplified Memory bounded A * (SMA *)<\/a><\/li>\n<li><a href=\"https:\/\/www.semanticscholar.org\/paper\/Real-Time-Heuristic-Search-Korf\/2fda10f6079156c4621fefc8b7cad72c1829ee94?p2df\" target=\"_blank\" rel=\"noopener\">Realtime A *<\/a><\/li>\n<li><a href=\"http:\/\/web.cs.du.edu\/~sturtevant\/papers\/TBA.pdf\" target=\"_blank\" rel=\"noopener\">Time-Bounded A * (TBA *)<\/a><\/li>\n<\/ul>\n<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5772\" class=\"elementor-tab-title\" data-tab=\"2\" role=\"button\" aria-controls=\"elementor-tab-content-5772\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">II. Shortest path, multiple sources<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5772\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"2\" role=\"region\" aria-labelledby=\"elementor-tab-title-5772\"><ul>\n<li>Undirected graph\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/floyd-warshall-transitive-closure-algorithm\/\">Floyd-Warshall algorithm<\/a><\/li>\n<\/ul>\n<ul>\n<li><a href=\"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000085710781\" target=\"_blank\" rel=\"noopener\">Seidel<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Williams<\/a><\/li>\n<li><a href=\"https:\/\/archive.org\/details\/proceedingsofthi2002acms\/page\/267\" target=\"_blank\" rel=\"noopener\">Pettie &amp; Ramachandran<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Thorup<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Directed graph\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/floyd-warshall-transitive-closure-algorithm\/\">Floyd-Warshall algorithm<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Williams<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/johnson-algorithm\/\">Dijkstra with binary heap<\/a><\/li>\n<li><a href=\"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S030439750300402X\" target=\"_blank\" rel=\"noopener\">Pettie<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Hagerup<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Stochastic graph\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/\">Viterbi (see stochastic process)<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/markov-process\/\">Backward-Forward (see stochastic process)<\/a><\/li>\n<\/ul>\n<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5773\" class=\"elementor-tab-title\" data-tab=\"3\" role=\"button\" aria-controls=\"elementor-tab-content-5773\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">III. Shortest path, angle and navigation<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5773\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"3\" role=\"region\" aria-labelledby=\"elementor-tab-title-5773\"><ul>\n<li>A * -based\n<ul>\n<li><a href=\"http:\/\/robots.stanford.edu\/isrr-papers\/final\/final-23.pdf\" target=\"_blank\" rel=\"noopener\">Field D *<\/a><\/li>\n<li><a href=\"http:\/\/idm-lab.org\/bib\/abstracts\/papers\/aaai07a.pdf\" target=\"_blank\" rel=\"noopener\">Theta *<\/a><\/li>\n<li><a href=\"https:\/\/webdocs.cs.ualberta.ca\/~holte\/Publications\/aaai11PeterYapFinal.pdf\" target=\"_blank\" rel=\"noopener\">Block A *<\/a><\/li>\n<li><a href=\"http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.70.9276&amp;rep=rep1&amp;type=pdf\" target=\"_blank\" rel=\"noopener\">Multi-resolution Field D *<\/a><\/li>\n<li><a href=\"https:\/\/www.aaai.org\/ocs\/index.php\/ICAPS\/ICAPS13\/paper\/viewFile\/6060\/6194\" target=\"_blank\" rel=\"noopener\">ANYA<\/a><\/li>\n<li><a href=\"https:\/\/www.aaai.org\/ocs\/index.php\/ICAPS\/ICAPS16\/paper\/view\/13049\" target=\"_blank\" rel=\"noopener\">Recursive Strict Theta *<\/a><\/li>\n<li><a href=\"https:\/\/www.cambridge.org\/core\/journals\/robotica\/article\/abs\/cwave-theory-and-practice-of-a-fast-singlesource-anyangle-path-planning-algorithm\/15B1D45E7C4467A0C33020525ABD9B33\" target=\"_blank\" rel=\"noopener\">CWave<\/a><\/li>\n<\/ul>\n<\/li>\n<li>RRT-based\n<ul>\n<li><a href=\"https:\/\/arxiv.org\/abs\/1005.0416\" target=\"_blank\" rel=\"noopener\">Rapidly-exploring random graph (RRG)<\/a><\/li>\n<li><a href=\"https:\/\/arxiv.org\/abs\/1105.1186\" target=\"_blank\" rel=\"noopener\">RRT *<\/a><\/li>\n<li><a href=\"https:\/\/ieeexplore.ieee.org\/document\/6942976\/\" target=\"_blank\" rel=\"noopener\">Informed RRT *<\/a><\/li>\n<\/ul>\n<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5774\" class=\"elementor-tab-title\" data-tab=\"4\" role=\"button\" aria-controls=\"elementor-tab-content-5774\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">IV. Solvers<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5774\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"4\" role=\"region\" aria-labelledby=\"elementor-tab-title-5774\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/shortest-path-resolution-with-excel\/\">Shortest path resolution with Excel<\/a><\/li>\n<li>Switch from a multi-source \/ sink to a single<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\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-e0897ee elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e0897ee\" 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-45fe2293\" data-id=\"45fe2293\" 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-2364a569 elementor-widget elementor-widget-text-editor\" data-id=\"2364a569\" 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\">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\/#Recherche-de-chemin\" >Path search<\/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\/#Probleme-sous-optimal\" >Suboptimal problem<\/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\/#Arbre-de-chemins\" >Tree of paths<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Recherche-de-chemin\"><\/span>Path search<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>The <b>path search<\/b>, commonly called <i><b><span lang=\"en\" xml:lang=\"en\">pathfinding <\/span><\/b><\/i>consists in finding how to move in an environment between a starting point and an ending point while taking into account various constraints.<\/p>\n<p><\/p>\n<p><strong>Definition of a valued graph<\/strong><\/p>\n<p>A valued graph is a graph with the arcs of which we associate a real number called the length of the arc.<\/p>\n<p>We denote by w (x, y) the length of the arc (x, y) between the vertices x and y.<\/p>\n<p><\/p>\n<p>By analogy with the adjacency matrix, we can represent a graph valued by a square matrix, the coefficients of which correspond to the valuation of the arcs.<\/p>\n<p><\/p>\n<p>Let be a valued graph whose vertices have been numbered from 1 to n. The valuation matrix of G is the square matrix M = m<sub>ij<\/sub>, of size n * n, defined by<\/p>\n<p><\/p>\n<div>\n<figure><img decoding=\"async\" class=\"alignnone wp-image-427 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/131.png\" alt=\"pathfinding pathfinding shortest path graph theory\" width=\"277\" height=\"77\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p>Here is an example:<\/p>\n<p><\/p>\n<div>\n<figure><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-425 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/14.png\" alt=\"pathfinding pathfinding shortest path graph theory\" width=\"530\" height=\"150\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/14.png 530w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/14-300x85.png 300w\" sizes=\"(max-width: 530px) 100vw, 530px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p>We can therefore deduce the following linear program, with x<sub>ij<\/sub>= 1 if the arc is part of the shortest path, 0 otherwise:<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>minimize <img decoding=\"async\" class=\"alignnone\" src=\"https:\/\/upload.wikimedia.org\/math\/c\/c\/0\/cc0b9c5d99fd91926a1b436785781cf1.png\" alt=\"shortest path search path\" width=\"82\" height=\"40\" title=\"\"> with A the set of arcs<\/li>\n<li>subject to <img loading=\"lazy\" decoding=\"async\" class=\"alignnone\" src=\"https:\/\/upload.wikimedia.org\/math\/d\/7\/b\/d7b89f725185c1fd9984123cbaa89612.png\" alt=\"shortest path search path\" width=\"47\" height=\"17\" title=\"\"><\/li>\n<\/ul>\n<p><\/p>\n<p>and for all <em>i<\/em>, <img loading=\"lazy\" decoding=\"async\" class=\"alignnone\" src=\"https:\/\/upload.wikimedia.org\/math\/8\/a\/c\/8acfff4159658f8e55922120c4f3e303.png\" alt=\"shortest path search path\" width=\"320\" height=\"84\" title=\"\"><\/p>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6292 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath.png\" alt=\"pathfinding pathfinding shortest path graph theory\" width=\"769\" height=\"521\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath.png 769w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath-300x203.png 300w\" sizes=\"(max-width: 769px) 100vw, 769px\" \/><\/figure>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6293 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath2.png\" alt=\"pathfinding pathfinding shortest path graph theory\" width=\"380\" height=\"431\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath2.png 380w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath2-265x300.png 265w\" sizes=\"(max-width: 380px) 100vw, 380px\" \/><\/figure>\n<p><\/p>\n<p>Although it is linear programming, this method can be very expensive in memory, and even impossible to set up in certain cases (for example if it is about a distributed system). Another method of knowing the shortest path would be to know the smallest of all the paths from one vertex to another.<\/p>\n<p><\/p>\n<p>We define the weight of a path <strong>c = (u,\u2026, v)<\/strong><\/p>\n<p>as the sum of the weights of the arcs which constitute it noted <strong>w (c).<\/strong>We then define the minimum distance (shortest path) between two vertices u and v by:<\/p>\n<p><\/p>\n<div>\n<figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-413 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/12.png\" alt=\"pathfinding pathfinding shortest path graph theory\" width=\"466\" height=\"66\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/12.png 466w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/12-300x42.png 300w\" sizes=\"(max-width: 466px) 100vw, 466px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p>We would like to have a capable method, for any graph and for any pair of vertices <em><strong>x<\/strong><\/em> and<em><strong> y<\/strong><\/em>, to determine the shortest path between them. For this, we must understand and characterize as well as possible the structure of a solution: what are the properties of a shorter path?<\/p>\n<p><\/p>\n<p><strong>Lemma of Koenig.<\/strong> A shorter path between 2 vertices is elementary. A path is elementary if each of the peaks of the route is visited only once.<\/p>\n<p><\/p>\n<p>Listing all the paths to determine the shortest one reveals a serious flaw: its execution time. If the number of elementary paths is finite, it nonetheless remains very large, of the order of <em><strong>not!<\/strong><\/em> on an order graph <em><strong>not<\/strong><\/em>.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Probleme-sous-optimal\"><\/span>Suboptimal problem<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>We need a second, fundamental property, the <em>suboptimality (see Dynamic Programming)<\/em>. It is a matter of noticing that being a shorter path is recursive: a sequence of a shorter path is still a shorter path between its ends. Or if the fastest route between <em><strong>u <\/strong><\/em>and <em><strong>v<\/strong><\/em> goes through 2 peaks <em><strong>x<\/strong><\/em> and <em><strong>y<\/strong><\/em>, this route necessarily takes the shortest path between <em><strong>x<\/strong><\/em> and <em><strong>y.<\/strong><\/em><\/p>\n<p><\/p>\n<p>Yes <em><strong>p = (u,\u2026, v)<\/strong><\/em> is a shorter way between <em><strong>u<\/strong><\/em> and <em><strong>v<\/strong><\/em>, then for any summit <em><strong>x<\/strong><\/em> on the road <em><strong>p<\/strong><\/em> :<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>the subpath of <em><strong>p<\/strong><\/em> up to <em><strong>x<\/strong><\/em>, <em><strong>(u,\u2026, x)<\/strong><\/em>, is a shorter path of <em><strong>u<\/strong><\/em> To <em><strong>x<\/strong><\/em><\/li>\n<li>the subpath of <em><strong>p<\/strong><\/em> since <em><strong>x<\/strong><\/em>, <em><strong>(x,\u2026, v)<\/strong><\/em>, is a shorter path of <em><strong>x<\/strong><\/em> To <em><strong>v<\/strong><\/em><\/li>\n<\/ul>\n<p><\/p>\n<p>For the absurd let us suppose that there exists for example between <em><strong>u<\/strong><\/em> and <em><strong>x<\/strong><\/em> a path <em><strong>q<\/strong><\/em> of length strictly less than that of<em><strong> p = (u,\u2026, x,\u2026, v)<\/strong><\/em>. So we can build a new way <em><strong>p &#039;<\/strong><\/em> Between <em><strong>u<\/strong><\/em> and <em><strong>v<\/strong><\/em> substituting <em><strong>q<\/strong><\/em> on <em><strong>(u,\u2026, x)<\/strong><\/em> in the way <em><strong>p<\/strong><\/em>. The length of <em><strong>p &#039;<\/strong><\/em> is then strictly lower than that of <em><strong>p<\/strong><\/em>, which contradicts that <em><strong>p<\/strong><\/em> is a shorter way of <em><strong>u<\/strong><\/em> To <em><strong>v<\/strong><\/em>.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Arbre-de-chemins\"><\/span>Tree of paths<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>There is a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/\">tree<\/a> There is a tree showing the shortest paths from one starting point to all the others. Suppose the graph is connected, the edges are not directed, and the weights are non-negative. We develop a cloud of vertices, starting with s and eventually covering all the vertices. We store at each vertex v a label d (v) representing the distance of v from s in the subgraph made up of the cloud and its adjacent vertices. At each step: we add to the cloud the top outside the cloud with the smallest distance label; we update the labels of the vertices adjacent to u (see spanning tree).<\/p>\n<p><\/p>\n<p>Consider an edge e = (u, z) such that u is the most recently added vertex to the cloud and z is not in the cloud. The relaxation of edge e updates the distance d (z) as follows: d (z) \u2190 min {d (z), d (u) + weight (e)}<\/p>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6294 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/relax1.png\" alt=\"pathfinding pathfinding shortest path graph theory\" width=\"753\" height=\"322\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/relax1.png 753w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/relax1-300x128.png 300w\" sizes=\"(max-width: 753px) 100vw, 753px\" \/><\/figure>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6295 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/realx2.png\" alt=\"pathfinding pathfinding shortest path graph theory\" width=\"500\" height=\"500\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/realx2.png 500w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/realx2-300x300.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/realx2-150x150.png 150w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><\/figure>\n<p><\/p>\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>Theories Home page Wiki I. Shortest path, single source (path finding) Undirected graph Dijkstra&#039;s algorithm Dijkstra with binary heap Dijkstra with Fibonacci \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-362","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/362","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=362"}],"version-history":[{"count":40,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/362\/revisions"}],"predecessor-version":[{"id":20409,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/362\/revisions\/20409"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=362"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}