{"id":6887,"date":"2019-08-27T10:28:38","date_gmt":"2019-08-27T09:28:38","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6887"},"modified":"2022-12-03T23:02:06","modified_gmt":"2022-12-03T22:02:06","slug":"resolution-plus-court-chemin-avec-excel","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/shortest-path-resolution-with-excel\/","title":{"rendered":"Shortest path resolution with Excel"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6887\" class=\"elementor elementor-6887\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-59fb53c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"59fb53c\" 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-4df7c52\" data-id=\"4df7c52\" 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-1a3e380 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"1a3e380\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Path search<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-050d74f\" data-id=\"050d74f\" 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-9e063d5 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"9e063d5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-ef555dc\" data-id=\"ef555dc\" 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-83f3328 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"83f3328\" 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\/Probl%C3%A8me_de_plus_court_chemin\" 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-73fe3d69 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"73fe3d69\" 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-12a89ee3\" data-id=\"12a89ee3\" 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-1f257aeb elementor-widget elementor-widget-text-editor\" data-id=\"1f257aeb\" 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 class=\"tlid-input input\">\n<div class=\"source-wrap\">\n<div class=\"input-full-height-wrapper tlid-input-full-height-wrapper\">\n<div class=\"source-input\">\n<div class=\"source-footer-wrap source-or-target-footer\">\n<div class=\"character-count tlid-character-count\">\u00a0<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n<div class=\"tlid-results-container results-container\">\n<div class=\"tlid-result result-dict-wrapper\">\n<div class=\"result tlid-copy-target\">\n<div class=\"result-header\">\n<div class=\"starbutton jfk-button-flat jfk-button unstarred\" role=\"button\" aria-label=\"Enable translation tracking\">\n<div class=\"jfk-button-img\"><span style=\"color: var(--color-text);\">Let&#039;s use the solver in Excel to find the shortest path from node S to node T in an undirected network (there will be less constraints in a directed network).<\/span><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\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\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/shortest-path-resolution-with-excel\/#Formuler-le-probleme-de-plus-court-chemin-avec-Excel\" >Formulate the shortest path problem with Excel<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/shortest-path-resolution-with-excel\/#Resoudre-le-modele\" >Solve the model<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Formuler-le-probleme-de-plus-court-chemin-avec-Excel\"><\/span>Formulate the shortest path problem with Excel<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>To formulate this problem of <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/\">shortest way<\/a> with Excel, let&#039;s answer the following three questions.<\/p>\n\n<ul class=\"wp-block-list\">\n<li>What are the decisions to be made? For this problem, we need Excel to find out if an arc is on the shortest path or not (Yes = 1, No = 0). For example, if SB is part of the shortest path, cell F5 is equal to 1. Otherwise, cell F5 is equal to 0. (in yellow)<\/li>\n<li>What are the constraints on these decisions? The net flow (Outbound - Inbound) of each node must equal the supply - demand at that node. Node S should only have one outgoing arc (net flow = 1). Node T must have only one incoming arc (net flow = -1). All other nodes must have an outgoing arc and an incoming arc if the node is on the shortest path (net flow = 0) or without flow (net flow = 0). (in light blue)<\/li>\n<li>What is the overall measure of performance for these decisions? The overall measure of performance is the total distance of the shortest path, so the goal is to minimize this amount. (in dark blue)<\/li>\n<\/ul>\n\n<figure class=\"wp-block-image\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6869 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp45.png\" alt=\"shortest path resolution with excel\" width=\"604\" height=\"443\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp45.png 604w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp45-300x220.png 300w\" sizes=\"(max-width: 604px) 100vw, 604px\" \/><\/figure>\n\n<p>Let&#039;s name the following ranges:<\/p>\n\n<figure class=\"wp-block-table gridtable\">\n<table>\n<tbody>\n<tr>\n<th>Beach name<\/th>\n<th>Cells<\/th>\n<\/tr>\n<tr>\n<td>From<\/td>\n<td>B4: B21<\/td>\n<\/tr>\n<tr>\n<td>To<\/td>\n<td>C4: C21<\/td>\n<\/tr>\n<tr>\n<td>Distance<\/td>\n<td>D4: D21<\/td>\n<\/tr>\n<tr>\n<td>Go<\/td>\n<td>F4: F21<\/td>\n<\/tr>\n<tr>\n<td>NetFlow<\/td>\n<td>I4: I10<\/td>\n<\/tr>\n<tr>\n<td>SupplyDemand<\/td>\n<td>K4: K10<\/td>\n<\/tr>\n<tr>\n<td>TotalDistance<\/td>\n<td>F23<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>And let&#039;s insert the following functions:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6870 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp46.png\" alt=\"shortest path resolution with excel\" width=\"604\" height=\"443\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp46.png 604w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp46-300x220.png 300w\" sizes=\"(max-width: 604px) 100vw, 604px\" \/><\/figure>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Resoudre-le-modele\"><\/span>Solve the model<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Let\u2019s enter the solver parameters:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6871 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp47.png\" alt=\"shortest path resolution with excel\" width=\"570\" height=\"599\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp47.png 570w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp47-285x300.png 285w\" sizes=\"(max-width: 570px) 100vw, 570px\" \/><\/figure>\n<\/div>\n\n<p>The optimal solution is:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6872 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp48.png\" alt=\"shortest path resolution with excel\" width=\"604\" height=\"443\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp48.png 604w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/04\/lp48-300x220.png 300w\" sizes=\"(max-width: 604px) 100vw, 604px\" \/><\/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>Path Finder WIki Home Page Let&#039;s use the solver in Excel to find the shortest path from node S to node T... <\/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-6887","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6887","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=6887"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6887\/revisions"}],"predecessor-version":[{"id":17015,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6887\/revisions\/17015"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/362"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=6887"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}