{"id":48081,"date":"2021-03-05T10:05:16","date_gmt":"2021-03-05T09:05:16","guid":{"rendered":"https:\/\/datascientest.com\/?p=48081"},"modified":"2023-11-09T14:09:52","modified_gmt":"2023-11-09T14:09:52","slug":"algorithme-de-dijkstra","status":"publish","type":"post","link":"https:\/\/datascientest.com\/algorithme-de-dijkstra","title":{"rendered":"Algorithme de Dijkstra : comment trouver le plus court chemin ?"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-post\" data-elementor-id=\"48081\" class=\"elementor elementor-48081\" data-elementor-post-type=\"post\">\n\t\t\t\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-fd035d2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fd035d2\" data-element_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-ef89df0\" data-id=\"ef89df0\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2b13ec2 elementor-widget elementor-widget-heading\" data-id=\"2b13ec2\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\n.elementor-heading-title{padding:0;margin:0;line-height:1}.elementor-widget-heading .elementor-heading-title[class*=elementor-size-]>a{color:inherit;font-size:inherit;line-height:inherit}.elementor-widget-heading .elementor-heading-title.elementor-size-small{font-size:15px}.elementor-widget-heading .elementor-heading-title.elementor-size-medium{font-size:19px}.elementor-widget-heading .elementor-heading-title.elementor-size-large{font-size:29px}.elementor-widget-heading .elementor-heading-title.elementor-size-xl{font-size:39px}.elementor-widget-heading .elementor-heading-title.elementor-size-xxl{font-size:59px}<\/style><h2 class=\"elementor-heading-title elementor-size-default\">La th\u00e9orie des graphes est une branche des math\u00e9matiques et de l\u2019informatique qui consiste \u00e0 mod\u00e9liser diff\u00e9rents probl\u00e8mes de la vie r\u00e9elle sous forme de graphes. L\u2019une des utilisations les plus classiques est la mod\u00e9lisation d\u2019un r\u00e9seau routier entre diff\u00e9rentes villes. L\u2019une des probl\u00e9matiques principales \u00e9tant l\u2019optimisation des distances entre deux points. Pour trouver le plus court chemin , on utilise souvent l\u2019algorithme de Dijkstra. Revenons sur son fonctionnement dans cet article\nVoyons un exemple (tir\u00e9 de Wikipedia) :<\/h2>\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-651b380 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"651b380\" data-element_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-af73862\" data-id=\"af73862\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-714819b elementor-widget elementor-widget-image\" data-id=\"714819b\" data-element_type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\n.elementor-widget-image{text-align:center}.elementor-widget-image a{display:inline-block}.elementor-widget-image a img[src$=\".svg\"]{width:48px}.elementor-widget-image img{vertical-align:middle;display:inline-block}<\/style>\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"310\" height=\"282\" src=\"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/02\/pasted-image-0-6.png\" class=\"attachment-large size-large wp-image-48083\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/02\/pasted-image-0-6.png 310w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/02\/pasted-image-0-6-300x273.png 300w\" sizes=\"(max-width: 310px) 100vw, 310px\" \/>\t\t\t\t\t\t\t\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b1cff2e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b1cff2e\" data-element_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-8e7c314\" data-id=\"8e7c314\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f9a4480 elementor-widget elementor-widget-text-editor\" data-id=\"f9a4480\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\n.elementor-widget-text-editor.elementor-drop-cap-view-stacked .elementor-drop-cap{background-color:#69727d;color:#fff}.elementor-widget-text-editor.elementor-drop-cap-view-framed .elementor-drop-cap{color:#69727d;border:3px solid;background-color:transparent}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap{margin-top:8px}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap-letter{width:1em;height:1em}.elementor-widget-text-editor .elementor-drop-cap{float:left;text-align:center;line-height:1;font-size:50px}.elementor-widget-text-editor .elementor-drop-cap-letter{display:inline-block}<\/style>\t\t\t\t<p><span style=\"color: #000000;\"><span style=\"font-weight: 400;\">Ici les villes A \u00e0 J sont repr\u00e9sent\u00e9es par les <\/span><b>sommets<\/b><span style=\"font-weight: 400;\"> du graphe.<br \/><\/span><\/span><\/p><p><span style=\"color: #000000;\"><span style=\"font-weight: 400;\">Elles sont reli\u00e9es par des routes qui correspondent aux <\/span><b>ar\u00eates<\/b><span style=\"font-weight: 400;\"> du graphe. <\/span><\/span><span style=\"color: #000000;\"><span style=\"font-weight: 400;\">\u00c0 chaque ar\u00eate est associ\u00e9e une valeur que l\u2019on appelle le <\/span><b>poids<\/b><span style=\"font-weight: 400;\">. Elle correspond g\u00e9n\u00e9ralement \u00e0 un co\u00fbt ou \u00e0 une distance.<br \/><\/span><\/span><\/p><p><span style=\"font-weight: 400; color: #000000;\">Ici, chaque poids peut \u00eatre vu comme la distance entre les deux villes reli\u00e9es.<\/span><\/p>\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-63ce943 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"63ce943\" data-element_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-c22c705\" data-id=\"c22c705\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b8eacfc elementor-widget elementor-widget-heading\" data-id=\"b8eacfc\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Tr\u00e8s vite se pose un probl\u00e8me : comment d\u00e9terminer le plus court chemin entre deux sommets ? <\/h3>\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-15a400c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"15a400c\" data-element_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-06515ae\" data-id=\"06515ae\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-6e5e840 elementor-widget elementor-widget-text-editor\" data-id=\"6e5e840\" data-element_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<p><span style=\"font-weight: 400; color: #000000;\">C\u2019est l\u00e0 que l\u2019algorithme de Dijkstra intervient !\u00a0<\/span><\/p><p><b>Comment l\u2019algorithme Dijkstra fonctionne ?<\/b><\/p><p><span style=\"font-weight: 400; color: #000000;\">Imaginons que l\u2019on cherche \u00e0 trouver le plus court chemin entre la ville A et la ville J.<\/span><\/p><p><span style=\"font-weight: 400; color: #000000;\">Tout au long de l\u2019algorithme on va garder en m\u00e9moire le chemin le plus court depuis A pour chacune des autres villes dans un tableau.<\/span><\/p><p><span style=\"font-weight: 400; color: #000000;\">On r\u00e9p\u00e8te toujours le m\u00eame processus :<\/span><\/p><ol><li>On choisit le <strong>sommet accessible de distance<\/strong> minimale comme sommet \u00e0 explorer.<\/li><li>A partir de ce sommet, on <strong>explore ses voisins<\/strong> et on met \u00e0 jour les distances pour chacun. On ne met \u00e0 jour la distance que <strong>si elle est inf\u00e9rieure<\/strong> \u00e0 celle que l\u2019on avait auparavant<\/li><li>On <strong>r\u00e9p\u00e8te<\/strong> jusqu\u2019\u00e0 ce qu\u2019on arrive au <strong>point d\u2019arriv\u00e9e<\/strong> ou jusqu\u2019\u00e0 ce que <strong>tous les sommets<\/strong> aient \u00e9t\u00e9 <strong>explor\u00e9s<\/strong>.<\/li><\/ol><p>C\u2019est un peu vague tout \u00e7a \u2026<\/p>\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a21a846 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a21a846\" data-element_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-0662eb2\" data-id=\"0662eb2\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5057bd0 elementor-widget elementor-widget-heading\" data-id=\"5057bd0\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Et concr\u00e8tement \u00e7a donne quoi ?<\/h3>\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-63c30c8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"63c30c8\" data-element_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-98e8661\" data-id=\"98e8661\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c776a9d elementor-widget elementor-widget-video\" data-id=\"c776a9d\" data-element_type=\"widget\" data-settings=\"{&quot;youtube_url&quot;:&quot;https:\\\/\\\/youtu.be\\\/L4bidK4cASM&quot;,&quot;video_type&quot;:&quot;youtube&quot;,&quot;controls&quot;:&quot;yes&quot;}\" data-widget_type=\"video.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\n.elementor-widget-video .elementor-widget-container{overflow:hidden;transform:translateZ(0)}.elementor-widget-video .elementor-wrapper{aspect-ratio:var(--video-aspect-ratio)}.elementor-widget-video .elementor-wrapper iframe,.elementor-widget-video .elementor-wrapper video{height:100%;width:100%;display:flex;border:none;background-color:#000}@supports not (aspect-ratio:1\/1){.elementor-widget-video .elementor-wrapper{position:relative;overflow:hidden;height:0;padding-bottom:calc(100% \/ var(--video-aspect-ratio))}.elementor-widget-video .elementor-wrapper iframe,.elementor-widget-video .elementor-wrapper video{position:absolute;top:0;right:0;bottom:0;left:0}}.elementor-widget-video .elementor-open-inline .elementor-custom-embed-image-overlay{position:absolute;top:0;right:0;bottom:0;left:0;background-size:cover;background-position:50%}.elementor-widget-video .elementor-custom-embed-image-overlay{cursor:pointer;text-align:center}.elementor-widget-video .elementor-custom-embed-image-overlay:hover .elementor-custom-embed-play i{opacity:1}.elementor-widget-video .elementor-custom-embed-image-overlay img{display:block;width:100%;aspect-ratio:var(--video-aspect-ratio);-o-object-fit:cover;object-fit:cover;-o-object-position:center center;object-position:center center}@supports not (aspect-ratio:1\/1){.elementor-widget-video .elementor-custom-embed-image-overlay{position:relative;overflow:hidden;height:0;padding-bottom:calc(100% \/ var(--video-aspect-ratio))}.elementor-widget-video .elementor-custom-embed-image-overlay img{position:absolute;top:0;right:0;bottom:0;left:0}}.elementor-widget-video .e-hosted-video .elementor-video{-o-object-fit:cover;object-fit:cover}.e-con-inner>.elementor-widget-video,.e-con>.elementor-widget-video{width:var(--container-widget-width);--flex-grow:var(--container-widget-flex-grow)}<\/style>\t\t<div class=\"elementor-wrapper elementor-open-inline\">\n\t\t\t<div class=\"elementor-video\"><\/div>\t\t<\/div>\n\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-41afcfa elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"41afcfa\" data-element_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-2fa940e\" data-id=\"2fa940e\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-15926c2 elementor-widget elementor-widget-heading\" data-id=\"15926c2\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Conclusion<\/h3>\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-bfa8a9b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"bfa8a9b\" data-element_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-116f3fd\" data-id=\"116f3fd\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-395ed3a elementor-widget elementor-widget-text-editor\" data-id=\"395ed3a\" data-element_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<p><span style=\"color: #000000;\"><span style=\"font-weight: 400;\">Le tableau final nous donne la valeur du plus court chemin pour chacun des sommets du graphe. Par ailleurs, il garde en m\u00e9moire l\u2019origine du point pr\u00e9c\u00e9dent permettant d\u2019obtenir ce plus court chemin.<\/span><\/span><\/p><p><span style=\"font-weight: 400; color: #000000;\">Par exemple, pour le sommet G, la valeur 403C nous indique qu\u2019il faut 403 km pour l\u2019atteindre et que ce plus court chemin passe juste avant par le point C. Il suffit donc de remonter le tableau pour obtenir le plus court chemin pour n\u2019importe quel sommet.<\/span><\/p><p><span style=\"color: #000000;\">Cette particularit\u00e9 explique <strong>l\u2019int\u00e9r\u00eat de l\u2019algorithme de Dijkstra<\/strong> : une seule it\u00e9ration permet d\u2019obtenir le plus court chemin pour chaque sommet !<\/span><\/p>\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-42e00cf elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"42e00cf\" data-element_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-0b4ed52\" data-id=\"0b4ed52\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-333c107 elementor-widget elementor-widget-heading\" data-id=\"333c107\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Pour aller plus loin :<\/h3>\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-040048a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"040048a\" data-element_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-22c17a2\" data-id=\"22c17a2\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1b82314 elementor-widget elementor-widget-text-editor\" data-id=\"1b82314\" data-element_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<ul><li><span style=\"color: #000000;\"><span style=\"font-weight: 400;\">Il existe de nombreux autres algorithmes r\u00e9solvant le probl\u00e8me du plus court chemin. Il faut cependant<\/span><b> prendre garde aux conditions d\u2019application <\/b><span style=\"font-weight: 400;\">de ces diff\u00e9rents algorithmes. L\u2019algorithme de tri topologique par exemple est plus efficace que l\u2019algorithme de Dijkstra mais ne s\u2019applique qu\u2019\u00e0 des graphes acycliques (sans aucune boucle).<\/span><\/span><\/li><li>La <span style=\"color: #000000;\"><b>complexit\u00e9<\/b><\/span><span style=\"font-weight: 400;\"> de l\u2019algorithme de Dijkstra est polynomiale. Soit n le nombre de sommets et a le nombre d\u2019arcs, elle est dans le pire des cas en <\/span><span style=\"color: #000000;\"><b>O(a+ nlog(n))<\/b><\/span><\/li><li>Edsger Dijkstra a d\u00e9couvert cet algorithme en 20 minutes alors qu\u2019il cherchait la meilleure fa\u00e7on d\u2019aller de Rotterdam \u00e0 Groningen \u00e0 la terrasse d\u2019un caf\u00e9. Comme quoi <span style=\"color: #000000;\"><b>un caf\u00e9 peut r\u00e9soudre beaucoup de probl\u00e8mes<\/b>.<\/span><\/li><\/ul>\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e6a4456 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e6a4456\" data-element_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-d8d3f9c\" data-id=\"d8d3f9c\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c08b59a elementor-widget elementor-widget-text-editor\" data-id=\"c08b59a\" data-element_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<p>Cet article vous a plu ? Notre\u00a0<strong>formation Data Scientist<\/strong>\u00a0comporte un cours sur la th\u00e9orie des graphes. N&rsquo;attendez plus, <strong>d\u00e9couvrez le cursus<\/strong> !\u00a0<\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-253c15e elementor-align-center button-principale elementor-widget elementor-widget-button\" data-id=\"253c15e\" data-element_type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm elementor-animation-grow\" href=\"https:\/\/datascientest.com\/formation-data-scientist\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t<span class=\"elementor-button-text\">D\u00e9couvrir la formation Data Scientist<\/span>\n\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t<\/div>\n\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\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>La th\u00e9orie des graphes est une branche des math\u00e9matiques et de l\u2019informatique qui consiste \u00e0 mod\u00e9liser diff\u00e9rents probl\u00e8mes de la vie r\u00e9elle sous forme de graphes. L\u2019une des utilisations les plus classiques est la mod\u00e9lisation d\u2019un r\u00e9seau routier entre diff\u00e9rentes villes. L\u2019une des probl\u00e9matiques principales \u00e9tant l\u2019optimisation des distances entre deux points. Pour trouver le [&hellip;]<\/p>\n","protected":false},"author":77,"featured_media":53639,"comment_status":"open","ping_status":"open","sticky":false,"template":"elementor_theme","format":"standard","meta":{"content-type":"","inline_featured_image":false},"categories":[2497],"tags":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v21.7 (Yoast SEO v21.7) - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Algorithme de Dijkstra : comment trouver le plus court chemin ?<\/title>\n<meta name=\"description\" content=\"Vous vous \u00eates toujours demand\u00e9s comment les chemins les plus courts sont d\u00e9termin\u00e9 ? D\u00e9couvrez tout sur l&#039;algorithme de Dijkstra !\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/datascientest.com\/algorithme-de-dijkstra\" \/>\n<meta property=\"og:locale\" content=\"fr_FR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Algorithme de Dijkstra : comment trouver le plus court chemin ?\" \/>\n<meta property=\"og:url\" content=\"https:\/\/datascientest.com\/algorithme-de-dijkstra\" \/>\n<meta property=\"og:site_name\" content=\"Formation Data Science | DataScientest.com\" \/>\n<meta property=\"article:published_time\" content=\"2021-03-05T09:05:16+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-11-09T14:09:52+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/03\/illu_algo_dijkstra_blog-110.png\" \/>\n\t<meta property=\"og:image:width\" content=\"4267\" \/>\n\t<meta property=\"og:image:height\" content=\"2342\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"Raphael Kassel\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u00c9crit par\" \/>\n\t<meta name=\"twitter:data1\" content=\"Raphael Kassel\" \/>\n\t<meta name=\"twitter:label2\" content=\"Dur\u00e9e de lecture estim\u00e9e\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/datascientest.com\/algorithme-de-dijkstra\",\"url\":\"https:\/\/datascientest.com\/algorithme-de-dijkstra\",\"name\":\"Algorithme de Dijkstra : comment trouver le plus court chemin ?\",\"isPartOf\":{\"@id\":\"https:\/\/datascientest.com\/#website\"},\"datePublished\":\"2021-03-05T09:05:16+00:00\",\"dateModified\":\"2023-11-09T14:09:52+00:00\",\"author\":{\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1\"},\"description\":\"Vous vous \u00eates toujours demand\u00e9s comment les chemins les plus courts sont d\u00e9termin\u00e9 ? D\u00e9couvrez tout sur l'algorithme de Dijkstra !\",\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/datascientest.com\/algorithme-de-dijkstra\"]}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/datascientest.com\/#website\",\"url\":\"https:\/\/datascientest.com\/\",\"name\":\"Formation Data Science | DataScientest.com\",\"description\":\"Leader de la formation en Data Science\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/datascientest.com\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"fr-FR\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1\",\"name\":\"Raphael Kassel\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg\",\"contentUrl\":\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg\",\"caption\":\"Raphael Kassel\"},\"description\":\"Raphael Kassel est le Head of Data Programs chez DataScientest. Il supervise une \u00e9quipe Data, impl\u00e9mente de nouveaux parcours comme \\\"Chef de projet IA\\\" et \\\"Data Product Manager\\\", et contribue \u00e0 la modernisation des op\u00e9rations du groupe. En collaboration \u00e9troite avec l'\u00e9quipe de d\u00e9veloppement, il adapte l'accompagnement acad\u00e9mique aux \u00e9volutions de l'\u00e9quipe data et \u00e0 l'internationalisation.\",\"sameAs\":[\"https:\/\/www.linkedin.com\/in\/raphaelkassel\/\",\"Data Science\"],\"url\":\"https:\/\/datascientest.com\/author\/raphaelkassel\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Algorithme de Dijkstra : comment trouver le plus court chemin ?","description":"Vous vous \u00eates toujours demand\u00e9s comment les chemins les plus courts sont d\u00e9termin\u00e9 ? D\u00e9couvrez tout sur l'algorithme de Dijkstra !","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/datascientest.com\/algorithme-de-dijkstra","og_locale":"fr_FR","og_type":"article","og_title":"Algorithme de Dijkstra : comment trouver le plus court chemin ?","og_url":"https:\/\/datascientest.com\/algorithme-de-dijkstra","og_site_name":"Formation Data Science | DataScientest.com","article_published_time":"2021-03-05T09:05:16+00:00","article_modified_time":"2023-11-09T14:09:52+00:00","og_image":[{"width":4267,"height":2342,"url":"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/03\/illu_algo_dijkstra_blog-110.png","type":"image\/png"}],"author":"Raphael Kassel","twitter_card":"summary_large_image","twitter_misc":{"\u00c9crit par":"Raphael Kassel","Dur\u00e9e de lecture estim\u00e9e":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/datascientest.com\/algorithme-de-dijkstra","url":"https:\/\/datascientest.com\/algorithme-de-dijkstra","name":"Algorithme de Dijkstra : comment trouver le plus court chemin ?","isPartOf":{"@id":"https:\/\/datascientest.com\/#website"},"datePublished":"2021-03-05T09:05:16+00:00","dateModified":"2023-11-09T14:09:52+00:00","author":{"@id":"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1"},"description":"Vous vous \u00eates toujours demand\u00e9s comment les chemins les plus courts sont d\u00e9termin\u00e9 ? D\u00e9couvrez tout sur l'algorithme de Dijkstra !","inLanguage":"fr-FR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/datascientest.com\/algorithme-de-dijkstra"]}]},{"@type":"WebSite","@id":"https:\/\/datascientest.com\/#website","url":"https:\/\/datascientest.com\/","name":"Formation Data Science | DataScientest.com","description":"Leader de la formation en Data Science","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/datascientest.com\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"fr-FR"},{"@type":"Person","@id":"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1","name":"Raphael Kassel","image":{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/datascientest.com\/#\/schema\/person\/image\/","url":"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg","contentUrl":"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg","caption":"Raphael Kassel"},"description":"Raphael Kassel est le Head of Data Programs chez DataScientest. Il supervise une \u00e9quipe Data, impl\u00e9mente de nouveaux parcours comme \"Chef de projet IA\" et \"Data Product Manager\", et contribue \u00e0 la modernisation des op\u00e9rations du groupe. En collaboration \u00e9troite avec l'\u00e9quipe de d\u00e9veloppement, il adapte l'accompagnement acad\u00e9mique aux \u00e9volutions de l'\u00e9quipe data et \u00e0 l'internationalisation.","sameAs":["https:\/\/www.linkedin.com\/in\/raphaelkassel\/","Data Science"],"url":"https:\/\/datascientest.com\/author\/raphaelkassel"}]}},"_links":{"self":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts\/48081"}],"collection":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/users\/77"}],"replies":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/comments?post=48081"}],"version-history":[{"count":0,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts\/48081\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/media\/53639"}],"wp:attachment":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/media?parent=48081"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/categories?post=48081"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/tags?post=48081"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}