{"id":10768,"date":"2020-11-10T13:46:20","date_gmt":"2020-11-10T12:46:20","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=10768"},"modified":"2022-12-03T23:05:31","modified_gmt":"2022-12-03T22:05:31","slug":"corrected-exercises-shortest-path","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/corrected-exercises-shortest-path\/","title":{"rendered":"Corrected Exercises: Shortest Path"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"10768\" class=\"elementor elementor-10768\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d824fd6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d824fd6\" 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-271e618\" data-id=\"271e618\" 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-c4facf4 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"c4facf4\" 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-ae95ea8\" data-id=\"ae95ea8\" 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-5029e8a elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5029e8a\" 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-1903452\" data-id=\"1903452\" 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-262cf0a elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"262cf0a\" 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-e33471b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e33471b\" 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-2005434\" data-id=\"2005434\" 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-1e83ff3 elementor-widget elementor-widget-heading\" data-id=\"1e83ff3\" 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<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_83 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/corrected-exercises-shortest-path\/#Corrected-exercises-about-shortest-path-problems\" >Corrected exercises about shortest path problems<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/corrected-exercises-shortest-path\/#Exercise-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-path-search\/corrected-exercises-shortest-path\/#Exercise-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-path-search\/corrected-exercises-shortest-path\/#Exercise-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-path-search\/corrected-exercises-shortest-path\/#Exercise-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-path-search\/corrected-exercises-shortest-path\/#Exercise-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-path-search\/corrected-exercises-shortest-path\/#Exercise-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-path-search\/corrected-exercises-shortest-path\/#Exercise-7\" >Exercise 7<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Corrected-exercises-about-shortest-path-problems\"><\/span>Corrected exercises about shortest path problems<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-87adc2a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"87adc2a\" 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-82da03c\" data-id=\"82da03c\" 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-ad7f461 elementor-widget elementor-widget-text-editor\" data-id=\"ad7f461\" 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>This page presents several corrected exercises on shortest path problems. The exercises are mainly about shortest path for one source and shortest path from many sources.<\/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-fa519fb elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fa519fb\" 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-bbbecce\" data-id=\"bbbecce\" 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-5a9e4c5 elementor-widget elementor-widget-text-editor\" data-id=\"5a9e4c5\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-1\"><\/span><strong><b>Exercise 1<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>The air company Europa serves various European cities. The table below gives against the flight times between these cities.<br \/>\u2022 How to determine the fastest route between two cities?<br \/>\u2022 How to modify the previous method to take into account the duration of stopovers in different cities?<\/p><table><tbody><tr><td width=\"24\"><p>\u00a0<\/p><\/td><td width=\"42\"><p><strong><b>TO<\/b><\/strong><\/p><\/td><td width=\"42\"><p><strong><b>B<\/b><\/strong><\/p><\/td><td width=\"42\"><p><strong><b>VS<\/b><\/strong><\/p><\/td><td width=\"42\"><p><strong><b>D<\/b><\/strong><\/p><\/td><td width=\"42\"><p><strong><b>E<\/b><\/strong><\/p><\/td><\/tr><tr><td width=\"24\"><p><strong><b>TO<\/b><\/strong><\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><td width=\"42\"><p>1h30<\/p><\/td><td width=\"42\"><p>2h00<\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><td width=\"42\"><p>2h15<\/p><\/td><\/tr><tr><td width=\"24\"><p><strong><b>B<\/b><\/strong><\/p><\/td><td width=\"42\"><p>1h40<\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><td width=\"42\"><p>3h00<\/p><\/td><\/tr><tr><td width=\"24\"><p><strong><b>VS<\/b><\/strong><\/p><\/td><td width=\"42\"><p>2h20<\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><td width=\"42\"><p>2h55<\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><\/tr><tr><td width=\"24\"><p><strong><b>D<\/b><\/strong><\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><td width=\"42\"><p>3h20<\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><td width=\"42\"><p>1h05<\/p><\/td><\/tr><tr><td width=\"24\"><p><strong><b>E<\/b><\/strong><\/p><\/td><td width=\"42\"><p>2h25<\/p><\/td><td width=\"42\"><p>3h10<\/p><\/td><td width=\"42\"><p>1h10<\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><td width=\"42\"><p>\u00a0<\/p><\/td><\/tr><\/tbody><\/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-165b016 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"165b016\" 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-f13fb94\" data-id=\"f13fb94\" 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-27a4f6c elementor-widget elementor-widget-toggle\" data-id=\"27a4f6c\" 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-4151\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-4151\" 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-4151\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-4151\"><p>Simply draw the graph, whose vertices are cities and arcs the routes of the company, valuated each arc length of the corresponding flight. A shortest path algorithm then solves the problem.<br \/>To take into account the duration of stopovers, two methods are possible: Edit the previous algorithm, including in arcs the cost of stopover OR: each vertex is duplicated; an arc between them is the stopover of the corresponding city.<\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-10780 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8.png\" alt=\"corrected exercises on shortest path problems\" width=\"540\" height=\"136\" title=\"\" 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-e96f7c7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e96f7c7\" 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-1394876\" data-id=\"1394876\" 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-e704086 elementor-widget elementor-widget-text-editor\" data-id=\"e704086\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-2\"><\/span><strong><b>Exercise 2<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>We want to build a new plant in the following network, nodes are places and links represent costs to send energy from one place to another:<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-10781 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image9.png\" alt=\"corrected exercises on shortest path problems\" width=\"765\" height=\"478\" title=\"\" 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 <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/algorithm-of-dijkstra\/\">Dijkstra<\/a> algorithm, proposes a method to find the best place to build the plant, and then solve the problem with your method. Solve the problem with <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/floyd-warshall-transitive-closure-algorithm\/\">Floyd\u2013Warshall<\/a> algorithm.<\/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-eda943b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"eda943b\" 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-b576f63\" data-id=\"b576f63\" 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-9e84656 elementor-widget elementor-widget-toggle\" data-id=\"9e84656\" 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-1661\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1661\" 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-1661\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1661\"><p>We have to compute Dijkstra for each node (at source node). Once the tree of paths is created, sum up the cost of all paths from any node to the source node (sum the last shortest paths array). The best place is the minimum total weight of all Dijkstra occurrences. With Floyd-Warshall, the pseudo-closure matrix contains all arrays, just sum the inputs 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-95ac811 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"95ac811\" 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-6461349\" data-id=\"6461349\" 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-565a13c elementor-widget elementor-widget-text-editor\" data-id=\"565a13c\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-3\"><\/span><strong><b>Exercise 3<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>A robot moves in the following environment. It starts from the node labeled <em><i>start <\/i><\/em>and needs to reach the node labeled <em><i>end. <\/i><\/em>The environment is continuous and the scale is supplied on the figure. Considering the robot is a point, what is the shortest path from Start to End.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-10782 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image10.png\" alt=\"corrected exercises on shortest path problems\" width=\"581\" height=\"313\" title=\"\" 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-647ff97 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"647ff97\" 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-4a1d8c2\" data-id=\"4a1d8c2\" 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-2478ac0 elementor-widget elementor-widget-toggle\" data-id=\"2478ac0\" 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-3821\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-3821\" 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-3821\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-3821\"><p>Compute the Euclidian distance between the nodes. Draw the graph and apply Dijsktra&#039;s algorithm to find the shortest path from the node Star to the node End. Then draw the path on 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-e93bbb7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e93bbb7\" 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-ae573e3\" data-id=\"ae573e3\" 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-70ba247 elementor-widget elementor-widget-text-editor\" data-id=\"70ba247\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-4\"><\/span><strong><b>Exercise 4<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Considering the graph on exercise 1, edges are directed from left to right (or up to down) and weights are decreased by 4. How to find a minimal path from A to F? Solve it.<\/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-c6674d5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c6674d5\" 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-4f2e800\" data-id=\"4f2e800\" 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-f952249 elementor-widget elementor-widget-toggle\" data-id=\"f952249\" 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-2611\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2611\" 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-2611\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2611\"><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=\"aligncenter wp-image-10783 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image11.png\" alt=\"corrected exercises on shortest path problems\" width=\"550\" height=\"455\" title=\"\" 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-9de632f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9de632f\" 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-bd99fc1\" data-id=\"bd99fc1\" 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-9da6c1d elementor-widget elementor-widget-text-editor\" data-id=\"9da6c1d\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-5\"><\/span><strong><b>Exercise 5<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>(a) Calculate the shortest path from s to all other vertices by using the Dijkstra algorithm. Determine the shortest path tree.<\/p><p>(b) Is the shortest path tree unique?<\/p><p>(c) Now change the weight of the edge (3, 4) to \u22122. Show that the Dijkstra algorithm does not work in this case.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10784 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image12.png\" alt=\"corrected exercises on shortest path problems\" width=\"397\" height=\"189\" title=\"\" 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-eee411b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"eee411b\" 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-74bc708\" data-id=\"74bc708\" 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-c398f18 elementor-widget elementor-widget-toggle\" data-id=\"c398f18\" 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-2051\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2051\" 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-2051\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2051\"><p>(a) The solution is given by the following picture. The numbers next to vertices are the distances to the starting vertex and crossing out a number means that there has been an update. The numbers in squares indicate the final distances (shortest distances).<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10785 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image13.png\" alt=\"corrected exercises on shortest path problems\" width=\"349\" height=\"169\" title=\"\" 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) No shortest path tree is not unique. By substituting the edge (s, 3) with the edge (1, 2) one gets another shortest path tree.<\/p><p>(c) The Dijkstra 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). This is what happens: After visiting the vertices s, 1, 2 the algorithm will look for the shortest path to a not yet visited vertex. This will be vertex 4 with distance 6. After visiting vertex 4 the algorithm will not make an update on vertex 4 because it was already visited and for this reason not 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-24c52a6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"24c52a6\" 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-1cd1774\" data-id=\"1cd1774\" 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-ba4e3d1 elementor-widget elementor-widget-text-editor\" data-id=\"ba4e3d1\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-6\"><\/span><strong><b>Exercise 6<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>A man has to transport a wolf, a goat and a cabbage to the other side of a river. He has one boat to do this but it is so small that he can only take one of the three things with him each time. Is it possible to bring all three things to the other side of the river safely? Notice that the wolf and the goat or goat and the cabbage must never be on the same side of the river without surveillance of the man. At least the wolf is not vegetarian and does not 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-801bb24 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"801bb24\" 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-3767b76\" data-id=\"3767b76\" 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-9d5efd0 elementor-widget elementor-widget-toggle\" data-id=\"9d5efd0\" 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-1651\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1651\" 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-1651\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1651\"><p>We construct a graph for this problem where every legal state is represented by a vertex in the graph and look for a shortest path in that graph. So let S = {M, W, G, C} where M, W, G, C are the man, the wolf, the goat and the cabbage. A state for this problem is a pair (X, Y) where {X, Y} is a partition of S. The elements in X are still on the starting side of the river and the elements in 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 may not leave alone the cabbage and the wolf or the goat and the cabbage without surveillance. Now construct a graph G = (V, E) which has a vertex for every legal state of this problem. We have the directed edge (v1, v2) \u2208 E if we can get from the state v1 = (X1, Y1) to the state v2 = (X2, Y2) by just one boat trip across the river. All edges get the weight ce = 1. Now the problem can be solved by calculating the shortest path from the state (vertex) s = (S, \ud83d\ude09 to the state (vertex) t = (;, S). We get 7 as the solution for the shortest path.<\/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-cb5cfe5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"cb5cfe5\" 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-bc204f2\" data-id=\"bc204f2\" 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-43a229c elementor-widget elementor-widget-text-editor\" data-id=\"43a229c\" 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<h2><span class=\"ez-toc-section\" id=\"Exercise-7\"><\/span><strong><b>Exercise 7<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Consider the following modification of the Dijkstra&#039;s algorithm to work with negative weights: Determine the smallest weight c in \u2124 in the weighted graph G = (V, E, w), ie, the edge e st w (e) = c. Then for all edges f in E set w &#039;(f): = w (f) - 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 claim.<\/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-8618fc2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8618fc2\" 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-1fdfd9b\" data-id=\"1fdfd9b\" 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-466d49d elementor-widget elementor-widget-toggle\" data-id=\"466d49d\" 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-7381\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-7381\" 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-7381\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-7381\"><p>Now we claim that DJP does not work correctly on G &#039;because this modification does not maintain the shortest path property, ie, (-c) is a positive number, so you add it n times for an n-path. The following counter-example proves this:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10786 size-medium\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image14-300x97.png\" alt=\"corrected exercises on shortest path problems\" width=\"300\" height=\"97\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image14-300x97.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image14.png 399w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/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 Corrected exercises about shortest path problems This page presents several corrected exercises on shortest path problems. The exercises are \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":362,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"elementor_header_footer","meta":{"footnotes":""},"class_list":["post-10768","page","type-page","status-publish","hentry"],"amp_enabled":false,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/10768","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=10768"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/10768\/revisions"}],"predecessor-version":[{"id":19068,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/10768\/revisions\/19068"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/362"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=10768"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}