{"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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/ejercicios-corregidos-camino-mas-corto\/","title":{"rendered":"Ejercicios corregidos: camino m\u00e1s corto"},"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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/\">\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\">B\u00fasqueda de ruta<\/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\/es\/\">\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\">Pagina de inicio<\/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_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\">Contenido<\/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=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/ejercicios-corregidos-camino-mas-corto\/#Corrected-exercises-about-shortest-path-problems\" >Ejercicios corregidos sobre problemas del camino m\u00e1s corto.<\/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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/ejercicios-corregidos-camino-mas-corto\/#Exercise-1\" >Ejercicio 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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/ejercicios-corregidos-camino-mas-corto\/#Exercise-2\" >Ejercicio 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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/ejercicios-corregidos-camino-mas-corto\/#Exercise-3\" >Ejercicio 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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/ejercicios-corregidos-camino-mas-corto\/#Exercise-4\" >Ejercicio 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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/ejercicios-corregidos-camino-mas-corto\/#Exercise-5\" >Ejercicio 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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/ejercicios-corregidos-camino-mas-corto\/#Exercise-6\" >Ejercicio 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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/ejercicios-corregidos-camino-mas-corto\/#Exercise-7\" >Ejercicio 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>Ejercicios corregidos sobre problemas del camino m\u00e1s corto.<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>Esta p\u00e1gina presenta varios ejercicios corregidos sobre problemas del camino m\u00e1s corto. Los ejercicios tratan principalmente sobre el camino m\u00e1s corto para una fuente y el camino m\u00e1s corto de muchas fuentes.<\/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>Ejercicio 1<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>La compa\u00f1\u00eda a\u00e9rea Europa opera en varias ciudades europeas. La siguiente tabla muestra los tiempos de vuelo entre estas ciudades.<br \/>\u2022 \u00bfC\u00f3mo determinar la ruta m\u00e1s r\u00e1pida entre dos ciudades?<br \/>\u2022 \u00bfC\u00f3mo modificar el m\u00e9todo anterior para tener en cuenta la duraci\u00f3n de las escalas en diferentes ciudades?<\/p><table><tbody><tr><td width=\"24\"><p>\u00a0<\/p><\/td><td width=\"42\"><p><strong><b>PARA<\/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>mi<\/b><\/strong><\/p><\/td><\/tr><tr><td width=\"24\"><p><strong><b>PARA<\/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>mi<\/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\">Soluci\u00f3n<\/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>Simplemente dibuja la gr\u00e1fica, cuyos v\u00e9rtices son ciudades y arcos las rutas de la empresa, valora cada longitud de arco del vuelo correspondiente. Luego, un algoritmo de ruta m\u00e1s corta resuelve el problema.<br \/>Para tener en cuenta la duraci\u00f3n de las escalas, son posibles dos m\u00e9todos: Editar el algoritmo anterior, incluyendo en arcos el costo de la escala O: cada v\u00e9rtice se duplica; un arco entre ellos es la escala de la ciudad correspondiente.<\/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=\"Ejercicios corregidos sobre problemas del camino m\u00e1s corto.\" 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>Ejercicio 2<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Queremos construir una nueva planta en la siguiente red, los nodos son lugares y los enlaces representan costos para enviar energ\u00eda de un lugar a otro:<\/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=\"Ejercicios corregidos sobre problemas del camino m\u00e1s corto.\" 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>Residencia en <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-dijkstra\/\">Dijkstra<\/a> algoritmo, propone un m\u00e9todo para encontrar el mejor lugar para construir la planta y luego resuelve el problema con su m\u00e9todo. Resuelve el problema con <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-cierre-transitivo-floyd-warshall\/\">Floyd-Warshall<\/a> algoritmo.<\/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\">Soluci\u00f3n<\/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>Tenemos que calcular Dijkstra para cada nodo (en el nodo de origen). Una vez que se crea el \u00e1rbol de rutas, sume el costo de todas las rutas desde cualquier nodo hasta el nodo de origen (sume la \u00faltima matriz de rutas m\u00e1s cortas). El mejor lugar es el peso total m\u00ednimo de todas las ocurrencias de Dijkstra. Con Floyd-Warshall, la matriz de pseudo-cierre contiene todas las matrices, simplemente sume las entradas de cada matriz y encuentre el m\u00ednimo.<\/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>Ejercicio 3<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Un robot se mueve en el siguiente entorno. Comienza desde el nodo etiquetado <em><i>comienzo <\/i><\/em>y necesita llegar al nodo etiquetado <em><i>fin. <\/i><\/em>El entorno es continuo y la escala se suministra en la figura. Teniendo en cuenta que el robot es un punto, \u00bfcu\u00e1l es el camino m\u00e1s corto de principio a fin?<\/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=\"Ejercicios corregidos sobre problemas del camino m\u00e1s corto.\" 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\">Soluci\u00f3n<\/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>Calcule la distancia euclidiana entre los nodos. Dibuje el gr\u00e1fico y aplique el algoritmo de Dijsktra para encontrar la ruta m\u00e1s corta desde el nodo Estrella hasta el nodo Fin. Luego dibuja el camino en la figura.<\/p><table><tbody><tr><td width=\"102\"><p>Camino m\u00e1s corto<\/p><\/td><td width=\"102\"><p>Comienzo<\/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>Fin<\/p><\/td><\/tr><tr><td width=\"102\"><p>En eso<\/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>Comienzo<\/p><\/td><td width=\"102\"><p>\u2013<\/p><\/td><td width=\"102\"><p>ra\u00edz cuadrada 5<\/p><\/td><td width=\"102\"><p>ra\u00edz cuadrada 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>ra\u00edz cuadrada 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>ra\u00edz cuadrada 29 + ra\u00edz cuadrada 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>ra\u00edz cuadrada 29 + ra\u00edz cuadrada 17<\/p><\/td><\/tr><\/tbody><\/table><p>El camino m\u00e1s corto es 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>Ejercicio 4<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Considerando el gr\u00e1fico del ejercicio 1, los bordes se dirigen de izquierda a derecha (o de arriba a abajo) y los pesos se reducen en 4. \u00bfC\u00f3mo encontrar una ruta m\u00ednima de A a F? Resu\u00e9lvelo.<\/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\">Soluci\u00f3n<\/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>Aplicar <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-bellman\/\">botones<\/a> en este gr\u00e1fico (Un nodo est\u00e1 bloqueado solo si todos sus predecesores est\u00e1n bloqueados).<\/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=\"Ejercicios corregidos sobre problemas del camino m\u00e1s corto.\" 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>PARA<\/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>mi<\/p><\/td><td width=\"87\"><p>F<\/p><\/td><\/tr><tr><td width=\"87\"><p>en eso<\/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>Ejercicio 5<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>(a) Calcule la ruta m\u00e1s corta desde sa todos los dem\u00e1s v\u00e9rtices utilizando el algoritmo de Dijkstra. Determine el \u00e1rbol del camino m\u00e1s corto.<\/p><p>(b) \u00bfEs \u00fanico el \u00e1rbol del camino m\u00e1s corto?<\/p><p>(c) Ahora cambie el peso de la arista (3, 4) a -2. Muestre que el algoritmo de Dijkstra no funciona en este caso.<\/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=\"Ejercicios corregidos sobre problemas del camino m\u00e1s corto.\" 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\">Soluci\u00f3n<\/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) La soluci\u00f3n viene dada por la siguiente imagen. Los n\u00fameros junto a los v\u00e9rtices son las distancias al v\u00e9rtice inicial y tachar un n\u00famero significa que ha habido una actualizaci\u00f3n. Los n\u00fameros en cuadrados indican las distancias finales (distancias m\u00e1s cortas).<\/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=\"Ejercicios corregidos sobre problemas del camino m\u00e1s corto.\" 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) Ning\u00fan \u00e1rbol de camino m\u00e1s corto no es \u00fanico. Sustituyendo el borde (s, 3) con el borde (1, 2) se obtiene otro \u00e1rbol de ruta m\u00e1s corto.<\/p><p>(c) El algoritmo de Dijkstra dar\u00e1 la misma soluci\u00f3n que en el inciso (a) aunque la ruta (s, 1, 2, 3, 4) (dist 5) tiene una distancia m\u00e1s corta que la ruta (s, 1, 4) ( dist 6). Esto es lo que sucede: despu\u00e9s de visitar los v\u00e9rtices s, 1, 2, el algoritmo buscar\u00e1 el camino m\u00e1s corto hacia un v\u00e9rtice a\u00fan no visitado. Este ser\u00e1 el v\u00e9rtice 4 con distancia 6. Despu\u00e9s de visitar el v\u00e9rtice 4 el algoritmo no actualizar\u00e1 el v\u00e9rtice 4 porque ya fue visitado y por esta raz\u00f3n no encuentra el camino m\u00e1s corto (distancia 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>Ejercicio 6<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Un hombre tiene que transportar un lobo, una cabra y un repollo al otro lado de un r\u00edo. Tiene un bote para hacer esto, pero es tan peque\u00f1o que solo puede llevar una de las tres cosas con \u00e9l cada vez. \u00bfEs posible llevar las tres cosas al otro lado del r\u00edo de forma segura? Note que el lobo y la cabra o la cabra y el repollo nunca deben estar en el mismo lado del r\u00edo sin la vigilancia del hombre. Al menos el lobo no es vegetariano y no le gusta comer repollo.<\/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\">Soluci\u00f3n<\/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>Construimos un gr\u00e1fico para este problema donde cada estado legal est\u00e1 representado por un v\u00e9rtice en el gr\u00e1fico y buscamos la ruta m\u00e1s corta en ese gr\u00e1fico. Entonces, sea S = {M, W, G, C} donde M, W, G, C son el hombre, el lobo, la cabra y el repollo. Un estado para este problema es un par (X, Y) donde {X, Y} es una partici\u00f3n de S. Los elementos en X todav\u00eda est\u00e1n en el lado inicial del r\u00edo y los elementos en Y ya est\u00e1n en el otro lado. Un estado es un estado legal si W, G \u2208 X, Y \u21d2 M \u2208 X, Y y G, C \u2208 X, Y \u21d2 M \u2208 X, Y, no puedes dejar solo el repollo y el lobo o la cabra y el repollo sin vigilancia. Ahora construya una gr\u00e1fica G = (V, E) que tenga un v\u00e9rtice para cada estado legal de este problema. Tenemos el borde dirigido (v1, v2) \u2208 E si podemos pasar del estado v1 = (X1, Y1) al estado v2 = (X2, Y2) con solo un viaje en bote a trav\u00e9s del r\u00edo. Todas las aristas obtienen el peso ce = 1. Ahora el problema se puede resolver calculando el camino m\u00e1s corto desde el estado (v\u00e9rtice) s = (S, \ud83d\ude09 al estado (v\u00e9rtice) t = (;, S). Obtenemos 7 como la soluci\u00f3n para el camino m\u00e1s corto.<\/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>Ejercicio 7<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Considere la siguiente modificaci\u00f3n del algoritmo de Dijkstra para trabajar con pesos negativos: Determine el peso m\u00e1s peque\u00f1o c en \u2124 en el gr\u00e1fico ponderado G = (V, E, w), es decir, el borde e st w (e) = c. Entonces, para todas las aristas f en E, establezca w &#039;(f): = w (f) - c. Entonces G &#039;= (V, E, w&#039;) no tiene pesos negativos. \u00bfEsta versi\u00f3n del algoritmo funciona correctamente en este tipo de gr\u00e1fico? Demuestre su afirmaci\u00f3n.<\/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\">Soluci\u00f3n<\/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>Ahora afirmamos que DJP no funciona correctamente en G &#039;porque esta modificaci\u00f3n no mantiene la propiedad de la ruta m\u00e1s corta, es decir, (-c) es un n\u00famero positivo, por lo que se agrega n veces para una n-ruta. El siguiente contraejemplo lo demuestra:<\/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=\"Ejercicios corregidos sobre problemas del camino m\u00e1s corto.\" 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 Finder Wiki Homepage Ejercicios corregidos sobre problemas de camino m\u00e1s corto Esta p\u00e1gina presenta varios ejercicios corregidos sobre problemas de camino m\u00e1s corto. Los ejercicios son ... <\/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\/es\/wp-json\/wp\/v2\/pages\/10768","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=10768"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/10768\/revisions"}],"predecessor-version":[{"id":19068,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/10768\/revisions\/19068"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/362"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=10768"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}