{"id":15101,"date":"2022-04-17T07:31:23","date_gmt":"2022-04-17T06:31:23","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=15101"},"modified":"2024-02-11T19:42:25","modified_gmt":"2024-02-11T18:42:25","slug":"de-plus-court-chemin","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/problema-del-camino-mas-corto\/","title":{"rendered":"7 problemas del camino m\u00e1s corto"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"15101\" class=\"elementor elementor-15101\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e85d5ee elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e85d5ee\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-bcae4f4\" data-id=\"bcae4f4\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-cb6ed9c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"cb6ed9c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/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-f127814\" data-id=\"f127814\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5347077 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5347077\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/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-90f14fb\" data-id=\"90f14fb\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9a6d077 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"9a6d077\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Pathfinding\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-646991b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"646991b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-50343c2\" data-id=\"50343c2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ce945ff elementor-widget elementor-widget-text-editor\" data-id=\"ce945ff\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e33471b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e33471b\" data-element_type=\"section\"><div class=\"elementor-container elementor-column-gap-default\"><div class=\"elementor-row\"><div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2005434\" data-id=\"2005434\" data-element_type=\"column\"><div class=\"elementor-column-wrap elementor-element-populated\"><div class=\"elementor-widget-wrap\"><div class=\"elementor-element elementor-element-1e83ff3 elementor-widget elementor-widget-heading\" data-id=\"1e83ff3\" data-element_type=\"widget\" data-widget_type=\"heading.default\"><div class=\"elementor-widget-container\"><div id=\"ez-toc-container\" class=\"ez-toc-v2_0_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\">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\/teoria-de-grafos\/problema-del-camino-mas-corto\/#Exercices-corriges-de-probleme-de-plus-court-chemin\" >Ejercicios corregidos para el problema 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\/teoria-de-grafos\/problema-del-camino-mas-corto\/#Exercice-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\/teoria-de-grafos\/problema-del-camino-mas-corto\/#Exercice-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\/teoria-de-grafos\/problema-del-camino-mas-corto\/#Exercice-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\/teoria-de-grafos\/problema-del-camino-mas-corto\/#Exercice-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\/teoria-de-grafos\/problema-del-camino-mas-corto\/#Exercice-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\/teoria-de-grafos\/problema-del-camino-mas-corto\/#Exercice-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\/teoria-de-grafos\/problema-del-camino-mas-corto\/#Exercice-7\" >Ejercicio 7<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-corriges-de-probleme-de-plus-court-chemin\"><\/span>Ejercicios corregidos para el problema del camino m\u00e1s corto<span class=\"ez-toc-section-end\"><\/span><\/h2><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/section><section class=\"elementor-section elementor-top-section elementor-element elementor-element-87adc2a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"87adc2a\" data-element_type=\"section\"><div class=\"elementor-container elementor-column-gap-default\"><div class=\"elementor-row\"><div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-82da03c\" data-id=\"82da03c\" data-element_type=\"column\"><div class=\"elementor-column-wrap elementor-element-populated\"><div class=\"elementor-widget-wrap\"><div class=\"elementor-element elementor-element-ad7f461 elementor-widget elementor-widget-text-editor\" data-id=\"ad7f461\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\"><div class=\"elementor-widget-container\"><div class=\"elementor-text-editor elementor-clearfix\"><p>Esta p\u00e1gina presenta varios ejercicios corregidos sobre el problema de <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/\">camino m\u00e1s corto<\/a>. Los ejercicios se enfocan en el camino m\u00e1s corto hacia una fuente y el camino m\u00e1s corto desde m\u00faltiples fuentes.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"camino m\u00e1s corto camino m\u00e1s corto ejercicios corregidos dijkstra bellman ford-bellman\" width=\"97\" height=\"97\" title=\"\"><\/p><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/div><\/section>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f00ed9a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f00ed9a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-61b4367\" data-id=\"61b4367\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5151cb3 elementor-widget elementor-widget-heading\" data-id=\"5151cb3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-1\"><\/span>Ejercicio 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-91c9518 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"91c9518\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0958f1e\" data-id=\"0958f1e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-cde77e5 elementor-widget elementor-widget-text-editor\" data-id=\"cde77e5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\tLa aerol\u00ednea Europa opera en varias ciudades europeas. La siguiente tabla muestra los tiempos de vuelo entre estas ciudades. \u2022 \u00bfC\u00f3mo determinar la ruta m\u00e1s r\u00e1pida entre dos ciudades? \u2022 \u00bfC\u00f3mo modificar el m\u00e9todo anterior para tener en cuenta la duraci\u00f3n de las escalas en las diferentes ciudades?\n<table>\n<tbody>\n<tr>\n<td width=\"24\"><\/td>\n<td width=\"42\"><strong><b>PARA<\/b><\/strong><\/td>\n<td width=\"42\"><strong><b>B<\/b><\/strong><\/td>\n<td width=\"42\"><strong><b>VS<\/b><\/strong><\/td>\n<td width=\"42\"><strong><b>D<\/b><\/strong><\/td>\n<td width=\"42\"><strong><b>mi<\/b><\/strong><\/td>\n<\/tr>\n<tr>\n<td width=\"24\"><strong><b>PARA<\/b><\/strong><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">1h30<\/td>\n<td width=\"42\">2h00<\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">2h15<\/td>\n<\/tr>\n<tr>\n<td width=\"24\"><strong><b>B<\/b><\/strong><\/td>\n<td width=\"42\">1h40<\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">3h00<\/td>\n<\/tr>\n<tr>\n<td width=\"24\"><strong><b>VS<\/b><\/strong><\/td>\n<td width=\"42\">2h20<\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">2h55<\/td>\n<td width=\"42\"><\/td>\n<\/tr>\n<tr>\n<td width=\"24\"><strong><b>D<\/b><\/strong><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">3h20<\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\">1h05<\/td>\n<\/tr>\n<tr>\n<td width=\"24\"><strong><b>mi<\/b><\/strong><\/td>\n<td width=\"42\">2h25<\/td>\n<td width=\"42\">3h10<\/td>\n<td width=\"42\">1h10<\/td>\n<td width=\"42\"><\/td>\n<td width=\"42\"><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e93085a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e93085a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5a56ca8\" data-id=\"5a56ca8\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-82aa3b0 elementor-widget elementor-widget-toggle\" data-id=\"82aa3b0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1371\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1371\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1371\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1371\"><p>Solo dibuja el <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a>, cuyos v\u00e9rtices son las ciudades y los arcos las rutas de la empresa, valor\u00e1ndose en cada arco la longitud del vuelo correspondiente. A <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algoritmo<\/a> la 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 el costo de la escala en los arcos O: se duplica cada v\u00e9rtice; un arco entre ellos es la escala de la ciudad correspondiente.<\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-10780 size-full\" title=\"Ejercicios corregidos: Camino m\u00e1s corto 1\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8.png\" alt=\"camino m\u00e1s corto camino m\u00e1s corto ejercicios corregidos dijkstra bellman ford-bellman\" width=\"540\" height=\"136\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8.png 540w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8-300x76.png 300w\" sizes=\"(max-width: 540px) 100vw, 540px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-94bd183 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"94bd183\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-19af72f\" data-id=\"19af72f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a240326 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"a240326\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1ca8362 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1ca8362\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5405c3c\" data-id=\"5405c3c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a39c2f8 elementor-widget elementor-widget-heading\" data-id=\"a39c2f8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-2\"><\/span>Ejercicio 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4572433 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4572433\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ab813b2\" data-id=\"ab813b2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-48cef13 elementor-widget elementor-widget-text-editor\" data-id=\"48cef13\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Queremos construir una nueva f\u00e1brica en la siguiente red, los nodos son lugares y los enlaces representan los costos para enviar energ\u00eda de un lugar a otro:<\/p><p><img decoding=\"async\" class=\"alignnone wp-image-10781 size-full\" title=\"Ejercicios corregidos: Ruta m\u00e1s corta 2\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image9.png\" alt=\"camino m\u00e1s corto camino m\u00e1s corto ejercicios corregidos dijkstra bellman ford-bellman\" width=\"765\" height=\"478\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image9.png 765w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image9-300x187.png 300w\" sizes=\"(max-width: 765px) 100vw, 765px\" \/><\/p><p>Basado en el algoritmo de <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-dijkstra\/\">Dijkstra<\/a>, proponga un m\u00e9todo para encontrar el mejor lugar para construir la f\u00e1brica y luego resuelva el problema con su m\u00e9todo. Resolver el problema con el algoritmo de <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-cierre-transitivo-floyd-warshall\/\">Floyd-Warshall<\/a>.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-052dde0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"052dde0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2bcc14c\" data-id=\"2bcc14c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b61bcc5 elementor-widget elementor-widget-toggle\" data-id=\"b61bcc5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1901\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1901\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1901\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1901\"><p>Necesitamos calcular Dijkstra para cada nodo (en el nodo de origen). Una vez que se crea el \u00e1rbol de rutas, agregue el costo de todas las rutas desde cualquier nodo al nodo de origen (agregue 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 pseudocierre contiene todos los arreglos, simplemente sume las entradas de cada arreglo 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-eb88103 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"eb88103\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-83e40ef\" data-id=\"83e40ef\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3da1330 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"3da1330\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-abf59cc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"abf59cc\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7f92844\" data-id=\"7f92844\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b676906 elementor-widget elementor-widget-heading\" data-id=\"b676906\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-3\"><\/span>Ejercicio 3<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-111af08 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"111af08\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-09337ff\" data-id=\"09337ff\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f347ab4 elementor-widget elementor-widget-text-editor\" data-id=\"f347ab4\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Un robot se mueve a trav\u00e9s del siguiente entorno. Comienza desde el nodo etiquetado como inicio y debe llegar al nodo etiquetado como final. El entorno es continuo y la escala se proporciona en la figura. Considerando que el robot es un punto, \u00bfcu\u00e1l es el camino m\u00e1s corto de principio a fin?<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10782 size-full\" title=\"Ejercicios corregidos: Ruta m\u00e1s corta 3\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image10.png\" alt=\"camino m\u00e1s corto camino m\u00e1s corto ejercicios corregidos dijkstra bellman ford-bellman\" width=\"581\" height=\"313\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image10.png 581w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image10-300x162.png 300w\" sizes=\"(max-width: 581px) 100vw, 581px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0308110 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0308110\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7a95521\" data-id=\"7a95521\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-79321ef elementor-widget elementor-widget-toggle\" data-id=\"79321ef\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1271\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1271\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1271\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1271\"><p>Calcular la distancia euclidiana entre nodos. Dibuje el gr\u00e1fico y aplique el algoritmo de Dijkstra para encontrar la ruta m\u00e1s corta desde el nodo Estrella hasta el nodo Final. 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>La ruta m\u00e1s corta 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-6c7af00 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6c7af00\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-3a897a2\" data-id=\"3a897a2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d4dc108 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"d4dc108\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1c6c989 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1c6c989\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-14bb011\" data-id=\"14bb011\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-cfa15c0 elementor-widget elementor-widget-heading\" data-id=\"cfa15c0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-4\"><\/span>Ejercicio 4<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8abda4f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8abda4f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ffb2e29\" data-id=\"ffb2e29\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a1a702f elementor-widget elementor-widget-text-editor\" data-id=\"a1a702f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Considerando la gr\u00e1fica del ejercicio 1, las aristas se dirigen de izquierda a derecha (o de arriba hacia abajo) y los pesos se reducen en 4. \u00bfC\u00f3mo encontrar un camino m\u00ednimo de A a F? Resolver.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b3a331a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b3a331a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-08f48a7\" data-id=\"08f48a7\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-6421a2c elementor-widget elementor-widget-toggle\" data-id=\"6421a2c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1041\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1041\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1041\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1041\"><p>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=\"alignnone wp-image-10783 size-full\" title=\"Ejercicios corregidos: Ruta m\u00e1s corta 4\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image11.png\" alt=\"camino m\u00e1s corto camino m\u00e1s corto ejercicios corregidos dijkstra bellman ford-bellman\" width=\"550\" height=\"455\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image11.png 550w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image11-300x248.png 300w\" sizes=\"(max-width: 550px) 100vw, 550px\" \/><\/p><table><tbody><tr><td width=\"87\">\u00a0<\/td><td width=\"87\"><p>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-3de6061 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3de6061\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-784e2f5\" data-id=\"784e2f5\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-12d63f1 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"12d63f1\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a46d6ec elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a46d6ec\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4c31547\" data-id=\"4c31547\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-dc0ef4e elementor-widget elementor-widget-heading\" data-id=\"dc0ef4e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-5\"><\/span>Ejercicio 5<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4a0df76 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4a0df76\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-72ec163\" data-id=\"72ec163\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c23e994 elementor-widget elementor-widget-text-editor\" data-id=\"c23e994\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>(a) Calcule el camino m\u00e1s corto desde s hasta todos los dem\u00e1s v\u00e9rtices utilizando el algoritmo de Dijkstra. Determine el \u00e1rbol de ruta 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 \u22122. Demuestre que el algoritmo de Dijkstra no funciona en este caso.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10784 size-full\" title=\"Ejercicios corregidos: Ruta m\u00e1s corta 5\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image12.png\" alt=\"camino m\u00e1s corto camino m\u00e1s corto ejercicios corregidos dijkstra bellman ford-bellman\" width=\"397\" height=\"189\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image12.png 397w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image12-300x143.png 300w\" sizes=\"(max-width: 397px) 100vw, 397px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4e112df elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4e112df\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-95d3b75\" data-id=\"95d3b75\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c4ac7e6 elementor-widget elementor-widget-toggle\" data-id=\"c4ac7e6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2061\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2061\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2061\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2061\"><p>(a) La soluci\u00f3n viene dada por la siguiente imagen. Los n\u00fameros al lado de 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 los cuadrados indican las distancias finales (distancias m\u00e1s cortas).<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10785 size-full\" title=\"Ejercicios corregidos: Ruta m\u00e1s corta 6\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image13.png\" alt=\"camino m\u00e1s corto camino m\u00e1s corto ejercicios corregidos dijkstra bellman ford-bellman\" width=\"349\" height=\"169\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image13.png 349w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image13-300x145.png 300w\" sizes=\"(max-width: 349px) 100vw, 349px\" \/><\/p><p>(b) Ninguno <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/arboles-y-arboles\/\">\u00e1rbol<\/a> el camino m\u00e1s corto es \u00fanico. Reemplazando la arista (s, 3) por la arista (1, 2) obtenemos otro \u00e1rbol de caminos m\u00e1s cortos.<\/p><p>(c) El algoritmo de Dijkstra dar\u00e1 la misma soluci\u00f3n que en el inciso (a) aunque el camino (s, 1, 2, 3, 4) (dist 5) tiene una distancia m\u00e1s corta que el camino (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 a 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 se actualizar\u00e1 en el v\u00e9rtice 4 porque ya ha sido visitado y por esta raz\u00f3n no puede encontrar 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-09e8694 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"09e8694\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b9c0ef2\" data-id=\"b9c0ef2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-22c531e elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"22c531e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6589328 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6589328\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-05371cc\" data-id=\"05371cc\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1ffee78 elementor-widget elementor-widget-heading\" data-id=\"1ffee78\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-6\"><\/span>Ejercicio 6<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5a08bc6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5a08bc6\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d915bde\" data-id=\"d915bde\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-adf6abb elementor-widget elementor-widget-text-editor\" data-id=\"adf6abb\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Un hombre tiene que llevar un lobo, una cabra y un repollo a trav\u00e9s de un r\u00edo. Tiene un bote para hacerlo, 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? Tenga en cuenta que el lobo y la cabra o la cabra y el repollo nunca deben estar en el mismo lado del r\u00edo sin supervisi\u00f3n humana. 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-a33e925 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a33e925\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-3e06397\" data-id=\"3e06397\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-38f0972 elementor-widget elementor-widget-toggle\" data-id=\"38f0972\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5971\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5971\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5971\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5971\"><p>Construimos un gr\u00e1fico para este problema donde cada estado legal est\u00e1 representado por un v\u00e9rtice en el gr\u00e1fico y encontramos el camino m\u00e1s corto en este gr\u00e1fico. Sea S = {M,W,G, C} donde M,W,G, C son el hombre, el lobo, la cabra y el repollo.\u00a0<\/p><p>Un estado para este problema es un par (X, Y) donde {X, Y} es una partici\u00f3n de S. Los elementos de X siempre est\u00e1n en el lado inicial del r\u00edo y los elementos de 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 solos el repollo y el lobo o la cabra y el repollo desatendidos .\u00a0<\/p><p>Construyamos ahora un grafo G = (V, E) que tenga un v\u00e9rtice para cada estado legal de este problema. Tenemos la arista dirigida (v1, v2) \u2208 E si podemos pasar del estado v1 = (X1, Y1) al estado v2 = (X2, Y2) en un solo viaje en bote por el r\u00edo. Todas las aristas tienen un peso ce = 1. Ahora el problema se puede resolver calculando el camino m\u00e1s corto desde el estado (v\u00e9rtice) s = (S, -) hasta el estado (v\u00e9rtice) t = (-, S). Obtenemos 7 como la soluci\u00f3n de ruta m\u00e1s corta.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a62386b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a62386b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-414b386\" data-id=\"414b386\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8f0d77c elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"8f0d77c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0499051 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0499051\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2deefd0\" data-id=\"2deefd0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c19ede6 elementor-widget elementor-widget-heading\" data-id=\"c19ede6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-7\"><\/span>Ejercicio 7<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2b03d19 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2b03d19\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-9471bb3\" data-id=\"9471bb3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3b0eb59 elementor-widget elementor-widget-text-editor\" data-id=\"3b0eb59\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Considere la siguiente modificaci\u00f3n del algoritmo de Dijkstra para trabajar con pesos negativos: w(e) = c. Luego, para todas las aristas f en E establecemos w&#039;(f) := w(f) \u2013 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? Demuestra tu 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-feb7b8b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"feb7b8b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-30bb56a\" data-id=\"30bb56a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-fe1cd37 elementor-widget elementor-widget-toggle\" data-id=\"fe1cd37\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2661\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2661\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2661\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2661\"><p>Ahora afirmamos que el algoritmo no funciona bien en G&#039; porque esta modificaci\u00f3n no conserva la propiedad del camino m\u00e1s corto, es decir, (-c) es un n\u00famero positivo, por lo que suma n veces para obtener un camino n. El siguiente contraejemplo lo demuestra:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10786 size-full\" title=\"Ejercicios corregidos: Ruta m\u00e1s corta 7\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image14.png\" alt=\"camino m\u00e1s corto camino m\u00e1s corto ejercicios corregidos dijkstra bellman ford-bellman\" width=\"399\" height=\"129\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image14.png 399w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image14-300x97.png 300w\" sizes=\"(max-width: 399px) 100vw, 399px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Path Finding Wiki P\u00e1gina de inicio Ejercicios corregidos del problema de la ruta m\u00e1s corta Esta p\u00e1gina presenta varios ejercicios corregidos sobre el problema de la ruta m\u00e1s corta... <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-15101","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15101","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=15101"}],"version-history":[{"count":6,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15101\/revisions"}],"predecessor-version":[{"id":20385,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15101\/revisions\/20385"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=15101"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}