{"id":866,"date":"2016-01-29T15:15:21","date_gmt":"2016-01-29T14:15:21","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=866"},"modified":"2022-12-03T22:58:49","modified_gmt":"2022-12-03T21:58:49","slug":"algorithme-de-johnson","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-johnson-2\/","title":{"rendered":"Algoritmo de Johnson"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"866\" class=\"elementor elementor-866\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-63dd04a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"63dd04a\" 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-d3316af\" data-id=\"d3316af\" 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-9e73409 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"9e73409\" 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-ebb3744\" data-id=\"ebb3744\" 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-cdad408 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"cdad408\" 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-3decafe\" data-id=\"3decafe\" 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-8235095 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"8235095\" 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:\/\/fr.wikipedia.org\/wiki\/Algorithme_de_Johnson\" 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-4219b495 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4219b495\" 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-77e74f03\" data-id=\"77e74f03\" 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-279392b4 elementor-widget elementor-widget-text-editor\" data-id=\"279392b4\" 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\n<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\/algoritmo-johnson-2\/#Algorithme-de-Johnson\" >Algoritmo de Johnson<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-de-Johnson\"><\/span>Algoritmo de Johnson<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>El algoritmo de Johnson calcula los caminos m\u00e1s cortos para cualquier par de v\u00e9rtices en el <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a>. el tiene un buen <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/complejidad-en-el-tiempo\/\">complejidad<\/a> para gr\u00e1ficos dispersos (pocas aristas en comparaci\u00f3n con el n\u00famero de v\u00e9rtices).<\/p>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Utiliza los algoritmos de <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-dijkstra\/\">Dijkstra<\/a> y <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-ford-bellman-2\/\">botones vado<\/a>y devuelve la matriz de ponderaciones de ruta m\u00e1s corta o la afirmaci\u00f3n de que el gr\u00e1fico tiene una ruta de ponderaci\u00f3n negativa.<\/div>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">La t\u00e9cnica utilizada consiste en volver al caso solo con pesos positivos, luego ejecutar el algoritmo de Dijkstra partiendo de cada v\u00e9rtice. Si los pesos no son todos positivos, los redefinimos para poder reducirlos al primer caso.<\/div>\n\n<p>El algoritmo de Johnson consta de los siguientes pasos:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol style=\"text-align: justify;\">\n<li>Agregar un nuevo nodo <span class=\"texhtml\"><i>q<\/i><\/span> al gr\u00e1fico y conecte este nodo mediante arcos de peso cero a todos los dem\u00e1s nodos.<\/li>\n<li>Utilice el algoritmo Bellman-Ford a partir del nuevo nodo <span class=\"texhtml\"><i>q<\/i><\/span> para determinar, para cada v\u00e9rtice <span class=\"texhtml\"><i>v<\/i><\/span>, el peso m\u00ednimo <span class=\"texhtml\"><i>h<\/i>(<i>v<\/i>)<\/span> de un camino de <span class=\"texhtml\"><i>q<\/i><\/span> Para <span class=\"texhtml\"><i>v<\/i><\/span>. Si se detecta un ciclo negativo, el algoritmo se detiene en caso de falla.<\/li>\n<li><i>Responder<\/i> los arcos del gr\u00e1fico inicial utilizando los valores calculados por el algoritmo de Bellman-Ford: un arco de <span class=\"texhtml\"><i>tu<\/i><\/span> Para <span class=\"texhtml\"><i>v<\/i><\/span>, cuyo peso o longitud anterior es el n\u00famero <span class=\"texhtml\"><i>w (u, v)<\/i><\/span>, tiene para una nueva longitud el n\u00famero no negativo <span class=\"texhtml\"><i>w (u, v)<\/i> + <i>h (u)<\/i> - <i>H v)<\/i><\/span>.<\/li>\n<li>Quitar la tapa <span class=\"texhtml\"><i>q<\/i><\/span> y utilice el algoritmo de Dijkstra para determinar los caminos m\u00e1s cortos.<\/li>\n<\/ol>\n<\/div>\n\n<p>Ejemplo del algoritmo de Johnson:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-875 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/540px-johnsons_algorithm-svg.png\" alt=\"algoritmo de johnson de fuente \u00fanica de ruta m\u00e1s corta\" width=\"540\" height=\"215\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/540px-johnsons_algorithm-svg.png 540w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/540px-johnsons_algorithm-svg-300x119.png 300w\" sizes=\"(max-width: 540px) 100vw, 540px\" \/><\/figure>\n<\/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<\/div>","protected":false},"excerpt":{"rendered":"<p>B\u00fasqueda de caminos Wiki p\u00e1gina de inicio Algoritmo de Johnson El algoritmo de Johnson calcula los caminos m\u00e1s cortos para cualquier par de v\u00e9rtices en el gr\u00e1fico. \u00c9l \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":362,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-866","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/866","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=866"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/866\/revisions"}],"predecessor-version":[{"id":17922,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/866\/revisions\/17922"}],"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=866"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}