{"id":15101,"date":"2022-04-17T07:31:23","date_gmt":"2022-04-17T06:31:23","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=15101"},"modified":"2024-02-11T19:42:25","modified_gmt":"2024-02-11T18:42:25","slug":"de-plus-court-chemin","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/shortest-path-problem\/","title":{"rendered":"7 Shortest path problems"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"15101\" class=\"elementor elementor-15101\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e85d5ee elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e85d5ee\" 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-bcae4f4\" data-id=\"bcae4f4\" 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-cb6ed9c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"cb6ed9c\" 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-f127814\" data-id=\"f127814\" 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-5347077 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5347077\" 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-90f14fb\" data-id=\"90f14fb\" 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-9a6d077 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"9a6d077\" 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:\/\/en.wikipedia.org\/wiki\/Pathfinding\" 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-646991b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"646991b\" 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-50343c2\" data-id=\"50343c2\" 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-ce945ff elementor-widget elementor-widget-text-editor\" data-id=\"ce945ff\" 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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e33471b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e33471b\" data-element_type=\"section\"><div class=\"elementor-container elementor-column-gap-default\"><div class=\"elementor-row\"><div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2005434\" data-id=\"2005434\" data-element_type=\"column\"><div class=\"elementor-column-wrap elementor-element-populated\"><div class=\"elementor-widget-wrap\"><div class=\"elementor-element elementor-element-1e83ff3 elementor-widget elementor-widget-heading\" data-id=\"1e83ff3\" data-element_type=\"widget\" data-widget_type=\"heading.default\"><div class=\"elementor-widget-container\"><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-2\/shortest-path-problem\/#Exercices-corriges-de-probleme-de-plus-court-chemin\" >Exercises corrected for shortest path problem<\/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-2\/shortest-path-problem\/#Exercice-1\" >Exercise 1<\/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-2\/shortest-path-problem\/#Exercice-2\" >Exercise 2<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/shortest-path-problem\/#Exercice-3\" >Exercise 3<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/shortest-path-problem\/#Exercice-4\" >Exercise 4<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/shortest-path-problem\/#Exercice-5\" >Exercise 5<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/shortest-path-problem\/#Exercice-6\" >Exercise 6<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/shortest-path-problem\/#Exercice-7\" >Exercise 7<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-corriges-de-probleme-de-plus-court-chemin\"><\/span>Exercises corrected for shortest path problem<span class=\"ez-toc-section-end\"><\/span><\/h2><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/section><section class=\"elementor-section elementor-top-section elementor-element elementor-element-87adc2a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"87adc2a\" data-element_type=\"section\"><div class=\"elementor-container elementor-column-gap-default\"><div class=\"elementor-row\"><div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-82da03c\" data-id=\"82da03c\" data-element_type=\"column\"><div class=\"elementor-column-wrap elementor-element-populated\"><div class=\"elementor-widget-wrap\"><div class=\"elementor-element elementor-element-ad7f461 elementor-widget elementor-widget-text-editor\" data-id=\"ad7f461\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\"><div class=\"elementor-widget-container\"><div class=\"elementor-text-editor elementor-clearfix\"><p>This page presents several corrected exercises on the problem of <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/\">shortest way<\/a>. The exercises focus on the shortest path to one source and the shortest path from multiple sources.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"shortest path shortest path corrected exercises dijkstra bellman ford-bellman\" width=\"97\" height=\"97\" title=\"\"><\/p><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/section>\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-f00ed9a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f00ed9a\" 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-61b4367\" data-id=\"61b4367\" 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-5151cb3 elementor-widget elementor-widget-heading\" data-id=\"5151cb3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-1\"><\/span>Exercise 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-91c9518 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"91c9518\" 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-0958f1e\" data-id=\"0958f1e\" 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-cde77e5 elementor-widget elementor-widget-text-editor\" data-id=\"cde77e5\" 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\tThe Europa airline serves several European cities. The table below gives the flight times between these cities. \u2022 How to determine the fastest route between two cities? \u2022 How to modify the previous method to take into account the duration of stopovers in the different cities?\n<table>\n<tbody>\n<tr>\n<td width=\"24\"><\/td>\n<td width=\"42\"><strong><b>TO<\/b><\/strong><\/td>\n<td width=\"42\"><strong><b>B<\/b><\/strong><\/td>\n<td width=\"42\"><strong><b>VS<\/b><\/strong><\/td>\n<td width=\"42\"><strong><b>D<\/b><\/strong><\/td>\n<td width=\"42\"><strong><b>E<\/b><\/strong><\/td>\n<\/tr>\n<tr>\n<td width=\"24\"><strong><b>TO<\/b><\/strong><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">1h30<\/td>\n<td width=\"42\">2h00<\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">2h15<\/td>\n<\/tr>\n<tr>\n<td width=\"24\"><strong><b>B<\/b><\/strong><\/td>\n<td width=\"42\">1h40<\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">3h00<\/td>\n<\/tr>\n<tr>\n<td width=\"24\"><strong><b>VS<\/b><\/strong><\/td>\n<td width=\"42\">2h20<\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">2h55<\/td>\n<td width=\"42\"><\/td>\n<\/tr>\n<tr>\n<td width=\"24\"><strong><b>D<\/b><\/strong><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">3h20<\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">1h05<\/td>\n<\/tr>\n<tr>\n<td width=\"24\"><strong><b>E<\/b><\/strong><\/td>\n<td width=\"42\">2h25<\/td>\n<td width=\"42\">3h10<\/td>\n<td width=\"42\">1h10<\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\"><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\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-e93085a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e93085a\" 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-5a56ca8\" data-id=\"5a56ca8\" 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-82aa3b0 elementor-widget elementor-widget-toggle\" data-id=\"82aa3b0\" 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-1371\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1371\" 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\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1371\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1371\"><p>Just draw the <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a>, the vertices of which are the cities and the arcs the routes of the company, valued at each arc the length of the corresponding flight. A <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> shortest path then solves the problem.<br \/>To take into account the duration of stopovers, two methods are possible: Edit the previous algorithm, including the stopover cost in the arcs OR: each vertex is duplicated; an arc between them is the corresponding city stopover.<\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-10780 size-full\" title=\"Corrected Exercises: Shortest Path 1\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8.png\" alt=\"shortest path shortest path corrected exercises dijkstra bellman ford-bellman\" width=\"540\" height=\"136\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8.png 540w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8-300x76.png 300w\" sizes=\"(max-width: 540px) 100vw, 540px\" \/><\/p><\/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-94bd183 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"94bd183\" 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-19af72f\" data-id=\"19af72f\" 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-a240326 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"a240326\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-1ca8362 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1ca8362\" 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-5405c3c\" data-id=\"5405c3c\" 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-a39c2f8 elementor-widget elementor-widget-heading\" data-id=\"a39c2f8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-2\"><\/span>Exercise 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-4572433 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4572433\" 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-ab813b2\" data-id=\"ab813b2\" 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-48cef13 elementor-widget elementor-widget-text-editor\" data-id=\"48cef13\" 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<p>We want to build a new factory in the following network, the nodes are places and the links represent the costs to send energy from one place to another:<\/p><p><img decoding=\"async\" class=\"alignnone wp-image-10781 size-full\" title=\"Corrected Exercises: Shortest Path 2\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image9.png\" alt=\"shortest path shortest path corrected exercises dijkstra bellman ford-bellman\" width=\"765\" height=\"478\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image9.png 765w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image9-300x187.png 300w\" sizes=\"(max-width: 765px) 100vw, 765px\" \/><\/p><p>Based on the algorithm of <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/algorithm-of-dijkstra\/\">Dijkstra<\/a>, come up with a method to find the best place to build the factory, then solve the problem with your method. Solve the problem with the algorithm of <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/floyd-warshall-transitive-closure-algorithm\/\">Floyd\u2013Warshall<\/a>.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-052dde0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"052dde0\" 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-2bcc14c\" data-id=\"2bcc14c\" 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-b61bcc5 elementor-widget elementor-widget-toggle\" data-id=\"b61bcc5\" 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-1901\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1901\" 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\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1901\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1901\"><p>We need to calculate Dijkstra for each node (at source node). Once the path tree is created, add the cost of all paths from any node to the source node (add the last shortest paths array). The best place is the minimum total weight of all occurrences of Dijkstra. With Floyd-Warshall, the pseudo-closure matrix contains all arrays, just sum the entries of each array and find the minimum.<\/p><\/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-eb88103 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"eb88103\" 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-83e40ef\" data-id=\"83e40ef\" 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-3da1330 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"3da1330\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-abf59cc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"abf59cc\" 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-7f92844\" data-id=\"7f92844\" 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-b676906 elementor-widget elementor-widget-heading\" data-id=\"b676906\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-3\"><\/span>Exercise 3<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-111af08 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"111af08\" 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-09337ff\" data-id=\"09337ff\" 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-f347ab4 elementor-widget elementor-widget-text-editor\" data-id=\"f347ab4\" 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<p>A robot moves through the next environment. It starts from the node labeled start and must reach the node labeled end. The environment is continuous and the scale is provided in the figure. Considering the robot is a point, what is the shortest path from start to end.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10782 size-full\" title=\"Corrected Exercises: Shortest Path 3\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image10.png\" alt=\"shortest path shortest path corrected exercises dijkstra bellman ford-bellman\" width=\"581\" height=\"313\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image10.png 581w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image10-300x162.png 300w\" sizes=\"(max-width: 581px) 100vw, 581px\" \/><\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0308110 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0308110\" 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-7a95521\" data-id=\"7a95521\" 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-79321ef elementor-widget elementor-widget-toggle\" data-id=\"79321ef\" 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-1271\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1271\" 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\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1271\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1271\"><p>Calculate the Euclidean distance between nodes. Draw the graph and apply Dijkstra&#039;s algorithm to find the shortest path from Star node to End node. Then draw the path in the figure.<\/p><table><tbody><tr><td width=\"102\"><p>Shortest path<\/p><\/td><td width=\"102\"><p>Start<\/p><\/td><td width=\"102\"><p>1<\/p><\/td><td width=\"102\"><p>2<\/p><\/td><td width=\"102\"><p>3<\/p><\/td><td width=\"102\"><p>End<\/p><\/td><\/tr><tr><td width=\"102\"><p>Init<\/p><\/td><td width=\"102\"><p>0<\/p><\/td><td width=\"102\"><p>inf<\/p><\/td><td width=\"102\"><p>inf<\/p><\/td><td width=\"102\"><p>inf<\/p><\/td><td width=\"102\"><p>inf<\/p><\/td><\/tr><tr><td width=\"102\"><p>Start<\/p><\/td><td width=\"102\"><p>\u2013<\/p><\/td><td width=\"102\"><p>sqrt 5<\/p><\/td><td width=\"102\"><p>sqrt 29<\/p><\/td><td width=\"102\"><p>inf<\/p><\/td><td width=\"102\"><p>inf<\/p><\/td><\/tr><tr><td width=\"102\"><p>1<\/p><\/td><td width=\"102\"><p>\u2013<\/p><\/td><td width=\"102\"><p>\u2013<\/p><\/td><td width=\"102\"><p>sqrt 29<\/p><\/td><td width=\"102\"><p>sqrt 5+ sqrt 26<\/p><\/td><td width=\"102\"><p>inf<\/p><\/td><\/tr><tr><td width=\"102\"><p>2<\/p><\/td><td width=\"102\"><p>\u2013<\/p><\/td><td width=\"102\"><p>\u2013<\/p><\/td><td width=\"102\"><p>\u2013<\/p><\/td><td width=\"102\"><p>sqrt 5+ sqrt 26<\/p><\/td><td width=\"102\"><p>sqrt 29 + sqrt 17<\/p><\/td><\/tr><tr><td width=\"102\"><p>3<\/p><\/td><td width=\"102\"><p>\u2013<\/p><\/td><td width=\"102\"><p>\u2013<\/p><\/td><td width=\"102\"><p>\u2013<\/p><\/td><td width=\"102\"><p>\u2013<\/p><\/td><td width=\"102\"><p>sqrt 29 + sqrt 17<\/p><\/td><\/tr><\/tbody><\/table><p>The shortest path is Start-2-End.<\/p><\/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-6c7af00 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6c7af00\" 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-3a897a2\" data-id=\"3a897a2\" 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-d4dc108 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"d4dc108\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-1c6c989 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1c6c989\" 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-14bb011\" data-id=\"14bb011\" 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-cfa15c0 elementor-widget elementor-widget-heading\" data-id=\"cfa15c0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-4\"><\/span>Exercise 4<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-8abda4f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8abda4f\" 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-ffb2e29\" data-id=\"ffb2e29\" 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-a1a702f elementor-widget elementor-widget-text-editor\" data-id=\"a1a702f\" 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<p>Considering the graph of exercise 1, the edges are directed from left to right (or from top to bottom) and the weights are decreased by 4. How to find a minimal path from A to F? Solve.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b3a331a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b3a331a\" 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-08f48a7\" data-id=\"08f48a7\" 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-6421a2c elementor-widget elementor-widget-toggle\" data-id=\"6421a2c\" 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-1041\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1041\" 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\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1041\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1041\"><p>Apply <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/bellman-algorithm\/\">Bellman<\/a> on this graph (A node is locked only if all its predecessors are locked).<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10783 size-full\" title=\"Corrected Exercises: Shortest Path 4\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image11.png\" alt=\"shortest path shortest path corrected exercises dijkstra bellman ford-bellman\" width=\"550\" height=\"455\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image11.png 550w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image11-300x248.png 300w\" sizes=\"(max-width: 550px) 100vw, 550px\" \/><\/p><table><tbody><tr><td width=\"87\">\u00a0<\/td><td width=\"87\"><p>TO<\/p><\/td><td width=\"87\"><p>B<\/p><\/td><td width=\"87\"><p>VS<\/p><\/td><td width=\"87\"><p>D<\/p><\/td><td width=\"87\"><p>E<\/p><\/td><td width=\"87\"><p>F<\/p><\/td><\/tr><tr><td width=\"87\"><p>init<\/p><\/td><td width=\"87\"><p>0<\/p><\/td><td width=\"87\"><p>inf<\/p><\/td><td width=\"87\"><p>inf<\/p><\/td><td width=\"87\"><p>inf<\/p><\/td><td width=\"87\"><p>inf<\/p><\/td><td width=\"87\"><p>inf<\/p><\/td><\/tr><tr><td width=\"87\"><p>A, 0<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>-1<\/p><\/td><td width=\"87\"><p>1<\/p><\/td><td width=\"87\"><p>5<\/p><\/td><td width=\"87\"><p>inf<\/p><\/td><td width=\"87\"><p>inf<\/p><\/td><\/tr><tr><td width=\"87\"><p>B, -1<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>-2<\/p><\/td><td width=\"87\"><p>-1<\/p><\/td><td width=\"87\"><p>2<\/p><\/td><td width=\"87\"><p>inf<\/p><\/td><\/tr><tr><td width=\"87\"><p>C, -2<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>-4<\/p><\/td><td width=\"87\"><p>0<\/p><\/td><td width=\"87\"><p>inf<\/p><\/td><\/tr><tr><td width=\"87\"><p>D, -4<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>-6<\/p><\/td><td width=\"87\"><p>-6<\/p><\/td><\/tr><tr><td width=\"87\"><p>E, -6<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>-6<\/p><\/td><\/tr><tr><td width=\"87\"><p>F<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><td width=\"87\"><p>\u2013<\/p><\/td><\/tr><\/tbody><\/table><\/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-3de6061 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3de6061\" 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-784e2f5\" data-id=\"784e2f5\" 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-12d63f1 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"12d63f1\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-a46d6ec elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a46d6ec\" 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-4c31547\" data-id=\"4c31547\" 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-dc0ef4e elementor-widget elementor-widget-heading\" data-id=\"dc0ef4e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-5\"><\/span>Exercise 5<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-4a0df76 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4a0df76\" 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-72ec163\" data-id=\"72ec163\" 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-c23e994 elementor-widget elementor-widget-text-editor\" data-id=\"c23e994\" 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<p>(a) Calculate the shortest path from s to all other vertices using Dijkstra&#039;s algorithm. Determine the shortest path tree.<\/p><p>(b) Is the shortest path tree unique?<\/p><p>(c) Now change the weight of edge (3, 4) to \u22122. Show that Dijkstra&#039;s algorithm does not work in this case.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10784 size-full\" title=\"Corrected Exercises: Shortest Path 5\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image12.png\" alt=\"shortest path shortest path corrected exercises dijkstra bellman ford-bellman\" width=\"397\" height=\"189\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image12.png 397w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image12-300x143.png 300w\" sizes=\"(max-width: 397px) 100vw, 397px\" \/><\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4e112df elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4e112df\" 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-95d3b75\" data-id=\"95d3b75\" 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-c4ac7e6 elementor-widget elementor-widget-toggle\" data-id=\"c4ac7e6\" 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-2061\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2061\" 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\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2061\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2061\"><p>(a) The solution is given by the following image. The numbers next to the vertices are the distances to the starting vertex and crossing out a number means there has been an update. The numbers in the squares indicate the final distances (shortest distances).<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10785 size-full\" title=\"Corrected Exercises: Shortest Path 6\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image13.png\" alt=\"shortest path shortest path corrected exercises dijkstra bellman ford-bellman\" width=\"349\" height=\"169\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image13.png 349w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image13-300x145.png 300w\" sizes=\"(max-width: 349px) 100vw, 349px\" \/><\/p><p>(b) None <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/\">tree<\/a> shortest path is unique. By replacing the edge (s, 3) by the edge (1, 2) we obtain another tree of shortest paths.<\/p><p>(c) Dijkstra&#039;s algorithm will give the same solution as in part (a) although the path (s, 1, 2, 3, 4) (dist 5) has a shorter distance than the path (s, 1 , 4) ( dist 6). Here&#039;s what happens: after visiting vertices s, 1, 2, the algorithm will search for the shortest path to a vertex not yet visited. This will be vertex 4 with distance 6. After visiting vertex 4, the algorithm will not update on vertex 4 because it has already been visited and for this reason cannot find the shortest path ( distance 5).<\/p><\/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-09e8694 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"09e8694\" 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-b9c0ef2\" data-id=\"b9c0ef2\" 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-22c531e elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"22c531e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-6589328 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6589328\" 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-05371cc\" data-id=\"05371cc\" 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-1ffee78 elementor-widget elementor-widget-heading\" data-id=\"1ffee78\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-6\"><\/span>Exercise 6<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-5a08bc6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5a08bc6\" 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-d915bde\" data-id=\"d915bde\" 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-adf6abb elementor-widget elementor-widget-text-editor\" data-id=\"adf6abb\" 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<p>A man has to carry a wolf, a goat and a cabbage across a river. He has a boat to do it with but it&#039;s so small he can only take one of the three things with him each time. Is it possible to get the three things across the river safely? Note that the Wolf and the Goat or the Goat and the Cabbage should never be on the same side of the river without human supervision. At least the wolf isn&#039;t a vegetarian and doesn&#039;t like to eat cabbage.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a33e925 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a33e925\" 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-3e06397\" data-id=\"3e06397\" 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-38f0972 elementor-widget elementor-widget-toggle\" data-id=\"38f0972\" 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-5971\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5971\" 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\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5971\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5971\"><p>We construct a graph for this problem where each legal state is represented by a vertex in the graph and find a shortest path in this graph. Let S = {M,W,G, C} where M,W,G, C are the man, the wolf, the goat and the cabbage.\u00a0<\/p><p>A state for this problem is a pair (X, Y ) where {X, Y } is a partition of S. The elements of X are always on the starting side of the river and the elements of Y are already on the other side . A state is a legal state if W,G \u2208 X, Y \u21d2 M \u2208 X, Y and G, C \u2208 X, Y \u21d2 M \u2208 X, Y, you cannot leave alone the cabbage and the wolf or the goat and cabbage unattended.\u00a0<\/p><p>Let us now construct a graph G = (V, E) which has a vertex for each legal state of this problem. We have the directed edge (v1 , v2 ) \u2208 E if we can go from state v1 = (X1 , Y1 ) to state v2 = (X2 , Y2 ) in a single boat trip on the river. All edges have weight ce = 1. Now the problem can be solved by calculating the shortest path from state (vertex) s = (S, -) to state (vertex) t = (-, S). We get 7 as the shortest path solution.<\/p><\/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-a62386b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a62386b\" 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-414b386\" data-id=\"414b386\" 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-8f0d77c elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"8f0d77c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-0499051 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0499051\" 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-2deefd0\" data-id=\"2deefd0\" 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-c19ede6 elementor-widget elementor-widget-heading\" data-id=\"c19ede6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-7\"><\/span>Exercise 7<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-2b03d19 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2b03d19\" 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-9471bb3\" data-id=\"9471bb3\" 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-3b0eb59 elementor-widget elementor-widget-text-editor\" data-id=\"3b0eb59\" 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<p>Consider the following modification of Dijkstra&#039;s algorithm for working with negative weights: w(e) = c. Then for all edges f in E we set w&#039;(f) := w(f) \u2013 c. Then G&#039;= (V,E,w&#039;) has no negative weights. Does this version of the algorithm work correctly on this type of graph? Prove your assertion.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-feb7b8b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"feb7b8b\" 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-30bb56a\" data-id=\"30bb56a\" 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-fe1cd37 elementor-widget elementor-widget-toggle\" data-id=\"fe1cd37\" 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-2661\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2661\" 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\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2661\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2661\"><p>Now we claim that the algorithm does not work well on G&#039; because this modification does not preserve the property of the shortest path, i.e. (-c) is a positive number, so you add n times for an n-path. The following counterexample proves this:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10786 size-full\" title=\"Corrected Exercises: Shortest Path 7\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image14.png\" alt=\"shortest path shortest path corrected exercises dijkstra bellman ford-bellman\" width=\"399\" height=\"129\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image14.png 399w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image14-300x97.png 300w\" sizes=\"(max-width: 399px) 100vw, 399px\" \/><\/p><\/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<\/div>","protected":false},"excerpt":{"rendered":"<p>Path Finding Wiki Home Page Shortest Path Problem Corrected Exercises This page presents several corrected exercises on the shortest path problem \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-15101","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15101","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=15101"}],"version-history":[{"count":6,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15101\/revisions"}],"predecessor-version":[{"id":20385,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/15101\/revisions\/20385"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=15101"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}