{"id":228,"date":"2011-09-28T18:12:26","date_gmt":"2011-09-28T21:12:26","guid":{"rendered":"http:\/\/www.taioque.com.br\/?p=228"},"modified":"2013-03-02T14:57:47","modified_gmt":"2013-03-02T17:57:47","slug":"228","status":"publish","type":"post","link":"http:\/\/www.networktips.com.br\/?p=228","title":{"rendered":"Algor\u00edtimo de Dijkstra"},"content":{"rendered":"<div style=\"padding-bottom:20px; padding-top:10px;\" class=\"hupso-share-buttons\"><!-- Hupso Share Buttons - https:\/\/www.hupso.com\/share\/ --><a class=\"hupso_toolbar\" href=\"https:\/\/www.hupso.com\/share\/\"><img src=\"http:\/\/static.hupso.com\/share\/buttons\/dot.png\" style=\"border:0px; padding-top: 5px; float:left;\" alt=\"Share Button\"\/><\/a><script type=\"text\/javascript\">var hupso_services_t=new Array(\"Twitter\",\"Facebook\",\"Google Plus\",\"Linkedin\",\"Email\");var hupso_background_t=\"#EAF4FF\";var hupso_border_t=\"#66CCFF\";var hupso_toolbar_size_t=\"medium\";var hupso_image_folder_url = \"\";var hupso_twitter_via=\"jorgeltaioque\";var hupso_url_t=\"\";var hupso_title_t=\"Algor%C3%ADtimo%20de%20Dijkstra\";<\/script><script type=\"text\/javascript\" src=\"http:\/\/static.hupso.com\/share\/js\/share_toolbar.js\"><\/script><!-- Hupso Share Buttons --><\/div><pre lang=\"php\" line=\"1\" escaped=\"true\">\r\n\/*\r\nJorge Luiz Taioque\r\njorge@lpnet.com.br\r\n*\/\r\n\r\n#include\r\n#include\r\n#include\r\n\r\nint destino, origem, vertices = 0;\r\nint custo, *custos = NULL;\r\n\r\nvoid calcula(int vertices,int origem,int destino,int *custos)\r\n{\r\nint i,v, contar = 0;\r\nint *ant, *tmp;\r\nint *z;\r\ndouble min;\r\ndouble dist[vertices];\r\n\r\n\/* criando matriz *\/\r\nant = calloc (vertices, sizeof(int *));\r\ntmp = calloc (vertices, sizeof(int *));\r\nif (ant == NULL) {\r\nprintf (\"Memoria Insuficiente\\n\");\r\nexit(-1);\r\n}\r\n\r\nz = calloc (vertices, sizeof(int *));\r\nif (z == NULL) {\r\nprintf (\"Memoria Insuficiente\\n\");\r\nexit(-1);\r\n}\r\n\r\nfor (i = 0; i &lt; vertices; i++) {\r\nif (custos[(origem - 1) * vertices + i] !=- 1) {\r\nant[i] = origem - 1;\r\ndist[i] = custos[(origem-1)*vertices+i];\r\n}\r\nelse {\r\nant[i]= -1;\r\ndist[i] = HUGE_VAL;\r\n}\r\nz[i]=0;\r\n}\r\nz[origem-1] = 1;\r\ndist[origem-1] = 0;\r\n\r\ndo {\r\n\r\nmin = HUGE_VAL;\r\nfor (i=0;i&lt;vertices;i++)\r\nif (!z[i])\r\nif (dist[i]&gt;=0 &amp;&amp; dist[i]&lt;min) {\r\nmin=dist[i];v=i;\r\n}\r\n\r\nif (min != HUGE_VAL &amp;&amp; v != destino - 1) {\r\nz[v] = 1;\r\nfor (i = 0; i &lt; vertices; i++)\r\nif (!z[i]) {\r\nif (custos[v*vertices+i] != -1 &amp;&amp; dist[v] + custos[v*vertices+i] &lt; dist[i]) {\r\ndist[i] = dist[v] + custos[v*vertices+i];\r\nant[i] =v;\r\n}\r\n}\r\n}\r\n} while (v != destino - 1 &amp;&amp; min != HUGE_VAL);\r\n\r\n\/*resultado da busca*\/\r\nprintf(\"\\tDe %d para %d: \\t\", origem, destino);\r\nif (min == HUGE_VAL) {\r\nprintf(\"Nao Existe\\n\");\r\nprintf(\"\\tCusto: \\t- \\n\");\r\n}\r\nelse {\r\ni = destino;\r\ni = ant[i-1];\r\nwhile (i != -1) {\r\ntmp[contar] = i+1;\r\ncontar++;\r\ni = ant[i];\r\n}\r\n\r\nfor (i = contar; i &gt; 0 ; i--) {\r\nprintf(\"%d -&gt; \", tmp[i-1]);\r\n}\r\nprintf(\"%d\", destino);\r\n\r\nprintf(\"\\n\\tCusto: %d\\n\",(int) dist[destino-1]);\r\n}\r\n}\r\n\r\nvoid limpar_tela(void)\r\n{\r\nsystem(\"clear\");\r\n}\r\n\r\nvoid menu(void)\r\n{\r\nlimpar_tela();\r\nprintf(\"Implementacao do Algoritmo de Dijasktra\\n\");\r\nprintf(\"Indice de comandos:\\n\");\r\nprintf(\"\\t a - Adicionar um Grafo\\n\"\r\n\"\\t g - Gera Caminhos\\n\"\r\n\"\\t CTRL+c - Sair\\n\");\r\nprintf(\"&gt;&gt;&gt;\");\r\n}\r\n\r\nvoid procurar(void)\r\n{\r\nint i, j;\r\n\r\nprintf(\"Caminhos mais curto: \\n\");\r\n\r\nfor (i = 1; i &lt;= vertices; i++) {\r\nfor (j = 1; j &lt;= vertices; j++)\r\ncalcula(vertices, i,j, custos);\r\nprintf(\"\\n\");\r\n}\r\n\r\nprintf(\"\\n\");\r\n}\r\n\r\nvoid adiciona_coordenadas(void)\r\n{\r\nint i, j;\r\n\r\ndo {\r\nprintf(\"\\nNumero de vertices (minimo 2 ): \\n\");\r\nprintf(\"&gt;&gt;&gt;\");\r\nscanf(\"%d\",&amp;vertices);\r\n} while (vertices &lt; 2 );\r\n\r\nif (!custos)\r\nfree(custos);\r\ncustos = (int *) malloc(sizeof(int)*vertices*vertices);\r\nfor (i = 0; i &lt;= vertices * vertices; i++)\r\ncustos[i] = -1;\r\n\r\nprintf(\"Quantidade de Arestas:\\n\");\r\ndo {\r\ndo {\r\nprintf(\"Origem da aresta (entre 1 e %d ou '0' para sair): \\n\", vertices);\r\nprintf(\"&gt;&gt;&gt;\");\r\nscanf(\"%d\",&amp;origem);\r\n} while (origem &lt; 0 || origem &gt; vertices);\r\n\r\nif (origem) {\r\ndo {\r\nprintf(\"Destino da aresta (entre 1 e %d, menos %d): \\n\", vertices, origem);\r\nprintf(\"&gt;&gt;&gt;\");\r\nscanf(\"%d\", &amp;destino);\r\n} while (destino &lt; 1 || destino &gt; vertices || destino == origem);\r\n\r\ndo {\r\nprintf(\"Custo da aresta %d para o vertice %d: \\n\",\r\norigem, destino);\r\nprintf(\"&gt;&gt;&gt;\");\r\nscanf(\"%d\",&amp;custo);\r\n} while (custo &lt; 0);\r\n\r\ncustos[(origem-1) * vertices + destino - 1] = custo;\r\n}\r\n\r\n} while (origem);\r\n}\r\n\r\nint main(int argc, char **argv) {\r\nint i, j;\r\nchar opcao[3], l[50];\r\n\r\ndo {\r\n\r\nmenu();\r\nscanf(\"%s\", &amp;opcao);\r\n\r\nif ((strcmp(opcao, \"a\")) == 0) {\r\nadiciona_coordenadas();\r\n}\r\n\r\nif ((strcmp(opcao, \"g\") == 0) &amp;&amp; (vertices &gt; 0) ) {\r\nprocurar();\r\n}\r\n\r\n} while (opcao != \"x\");\r\n\r\nprintf(\"\\n\\n\");\r\n\r\nreturn 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<div style=\"padding-bottom:20px; padding-top:10px;\" class=\"hupso-share-buttons\"><!-- Hupso Share Buttons - https:\/\/www.hupso.com\/share\/ --><a class=\"hupso_toolbar\" href=\"https:\/\/www.hupso.com\/share\/\"><img src=\"http:\/\/static.hupso.com\/share\/buttons\/dot.png\" style=\"border:0px; padding-top: 5px; float:left;\" alt=\"Share Button\"\/><\/a><script type=\"text\/javascript\">var hupso_services_t=new Array(\"Twitter\",\"Facebook\",\"Google Plus\",\"Linkedin\",\"Email\");var hupso_background_t=\"#EAF4FF\";var hupso_border_t=\"#66CCFF\";var hupso_toolbar_size_t=\"medium\";var hupso_image_folder_url = \"\";var hupso_twitter_via=\"jorgeltaioque\";var hupso_url_t=\"\";var hupso_title_t=\"Algor%C3%ADtimo%20de%20Dijkstra\";<\/script><script type=\"text\/javascript\" src=\"http:\/\/static.hupso.com\/share\/js\/share_toolbar.js\"><\/script><!-- Hupso Share Buttons --><\/div><p>\/* Jorge Luiz Taioque jorge@lpnet.com.br *\/ #include #include #include int destino, origem, vertices = 0; int custo, *custos = NULL; void calcula(int vertices,int origem,int destino,int *custos) { int i,v, contar = 0; int *ant, *tmp; int *z; double min; double &hellip; <a href=\"http:\/\/www.networktips.com.br\/?p=228\">Continue lendo <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[11],"tags":[],"_links":{"self":[{"href":"http:\/\/www.networktips.com.br\/index.php?rest_route=\/wp\/v2\/posts\/228"}],"collection":[{"href":"http:\/\/www.networktips.com.br\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.networktips.com.br\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.networktips.com.br\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.networktips.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=228"}],"version-history":[{"count":11,"href":"http:\/\/www.networktips.com.br\/index.php?rest_route=\/wp\/v2\/posts\/228\/revisions"}],"predecessor-version":[{"id":489,"href":"http:\/\/www.networktips.com.br\/index.php?rest_route=\/wp\/v2\/posts\/228\/revisions\/489"}],"wp:attachment":[{"href":"http:\/\/www.networktips.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=228"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.networktips.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=228"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.networktips.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=228"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}