Jump to content

Caio Thimons Silva Arruda

Members
  • Content count

    4
  • Joined

  • Last visited

Community Reputation

0 Comum

About Caio Thimons Silva Arruda

  1. Caio Thimons Silva Arruda

    conversão de .txt e arrays

    Boa Noite Pessoal,estou precisando de uma orientação na parte de .txt A página está incluindo a um arquivo.txt (cidade.txt), estou convertendo ela para todos os acentos sejam removidos, e fica tudo minúsculo, e convertendo ela em uma array, porém não sei se está correto essa conversão, poderiam me orientar ? Precisa que fica-se nesse modelo ("sao paulo","santos",10) Arquivo cidade.txt está com as seguintes configurações: São Carlos;Santos;10 Agradeço Deis e Já!! <?PHP include("Dijkstra.php"); // função onde lê todos os acentos, sem ele os acentos fica "bugado", pegue na NET. function utf8_fopen_read($fileName) { $fc = iconv('windows-1250', 'utf-8', file_get_contents($fileName)); $handle=fopen("php://memory", "rw"); fwrite($handle, $fc); fseek($handle, 0); return $handle; } // converter o arquivo . txt em uma array $arquivo = utf8_fopen_read ("cidade.txt", "r"); $Carray=array(); while (!feof ($arquivo)) { $linha = fgets($arquivo, 1024); $linha_modi = removeAccents($linha); $linha_modi2 = strtolower($linha_modi); $cidadeArray = $linha_modi2; $ListaArray = explode(";", "$cidadeArray", 3); echo("<br>teste<br>"); print_r($ListaArray); array_push($Carray, $ListaArray); } fclose($arquivo); //aqui é onde coloca a array, $Carray que está sendo puxando do arquivo .txt $graph_array = $Carray; // forma na qual o algoritmo funciona corretamente $Teste = array( array("sao carlos", "bauru", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9) ); echo("<br>Tem que ficar assim<br>"); print_r($Teste); $path = dijkstra($graph_array, "sao carlos", "itu"); $v= $path; $Km= $v["dados"]["km"]; $Array_Lista= $v["dados"]["Lista"]; $Lista = implode(" => ", $Array_Lista); echo("<br>Lista Aqui :<BR>"); echo $Lista; echo("<br>Km Aqui :<BR>"); echo $Km; ?>
  2. Caio Thimons Silva Arruda

    Algoritmo dijkstra menor distância

    Boa Noite Pessoal, consegui mexer bastante no código, porém estou precisando de ajuda na parte de .txt a pagina esta incluindo a cidade.txt, estou convertendo ela para todos os acentos seja removidos, e fica tudo minusculo, convertendo ela em uma array, porém não sei se esta correto essa conversão, poderiam verificar, ? precisa que fica-se nesse modelo ("sao paulo","santos",10) arquivo cidade.txt esta com as seguintes configurações: São Carlos;Santos;10 Alguma ideia ? <?PHP include("Dijkstra.php"); function utf8_fopen_read($fileName) { $fc = iconv('windows-1250', 'utf-8', file_get_contents($fileName)); $handle=fopen("php://memory", "rw"); fwrite($handle, $fc); fseek($handle, 0); return $handle; } $arquivo = utf8_fopen_read ("cidade.txt", "r"); $Carray=array(); while (!feof ($arquivo)) { $linha = fgets($arquivo, 1024); $linha_modi = removeAccents($linha); $linha_modi2 = strtolower($linha_modi); $cidadeArray = $linha_modi2; $ListaArray = explode(";", "$cidadeArray", 3); echo("<br>teste<br>"); print_r($ListaArray); array_push($Carray, $ListaArray); } fclose($arquivo); //aqui é onde coloca a array, $Carray esta puxando do arquivo .txt $graph_array = $Carray; // forma na qual o algoritmo funciona $Teste = array( array("sao carlos", "bauru", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9) ); echo("<br>Tem que ficar assim<br>"); print_r($Teste); $path = dijkstra($graph_array, "sao carlos", "itu"); $v= $path; $Km= $v["dados"]["km"]; $Array_Lista= $v["dados"]["Lista"]; $Lista = implode(" => ", $Array_Lista); echo("<br>Lista Aqui :<BR>"); echo $Lista; echo("<br>Km Aqui :<BR>"); echo $Km; ?>
  3. Caio Thimons Silva Arruda

    Algoritmo dijkstra menor distância

    Boa Tarde à todos, programa há um anos, porém estou com um problema na qual não sei como fazer, já procurei na net toda e principalmente aqui no iMasters, irei postar com mais detalhes: Estou fazendo um projeto da faculdade onde é buscar o menor caminho de uma rota, onde está sendo usado o algoritmo de Dijkstra, ele é formado em 2 páginas, index e resultado, o index o usuário pode colocar a cidade de origem e cidade de destino final, a página de resultado puxa a página do algoritmo, o projeto está funcionando corretamente, porém o Professor quer que eu puxo as cidades através de um arquivo .txt, já fiz alguns teste porém não funciona, irei posta as páginas: O Professor irá fornecer um arquivo .txt do seguinte modelo: São Paulo;Santos;100 O algoritmo funciona apenas com número, nesse modelo => ("1","2",100) Sendo 1 São Paulo e 2 Santos e 100 a distância de um para o outro. Precisa da ideia de alguém de como fazer essa conversão, já que não consegui mexer no algoritmo do Kijkstra para que aceita-se o nome da cidade, sendo que a array que ele aceita é("1","2",100); Alguém poderia me dar alguma ideia? , Agradeço deis de já Index: <!-- DISCIPLINA: GRAFOS E AUTÔMATOS --> <!doctype html> <html lang="pt-br"> <head> <link href='http://fonts.googleapis.com/css?family=Open+Sans:300,400,600,700' rel='stylesheet' type='text/css'> <link href='http://fonts.googleapis.com/css?family=Fjalla+One|Archivo+Narrow|Oswald:400,700' rel='stylesheet' type='text/css'> <link rel="stylesheet" href="css/reset.css" type="text/css" /> <link rel="stylesheet" href="css/style.css" type="text/css" /> </head> <title>GPS</title> <body> <header><div class="header"> <section><br/> <h1 align="center">Trabalho Grafo</h1> </section> </div></header> <div class="corpo_branco"> <br> <br> <br> <br> </div> <div class="corpo"> <aside> <h3>Sistema GPS</h3> <ol> <li>Cidade Origem.</li> <li>Cidade a ser deslocado.</li> <li>OBSERVAÇÕES:</li> <li>Sistema feito em PHP</li> <li>Sistema com Lista Adjacente</li> <li>Sistema com algoritmo Dijkstra</li> </ol> </aside> <div class="tabela" align="center"> <h2 align="center">GPS</h2> <table> <form name="form" action="resultado.php" method="post"> <tr> <td></td> <td>Informe a cidade local</td> </tr> <tr> <td><h4>Iniciar de :</h4></td> <td><select name="rota_de"> <option value="1"><h4>Araçariguama</option> <option value="2">Araraquara</option> <option value="3">Araras</option> <option value="4">Barra Bonita</option> <option value="5">Barueri</option> <option value="6">Boa Esperança do Sul</option> <option value="7">Botucatu</option> <option value="8">Brotas</option> <option value="9">Campinas</option> <option value="10">Cordeirópolis</option> <option value="11">Dois córregos</option> <option value="12">Dourado</option> <option value="13">Hortolândia</option> <option value="14">Ibaté</option> <option value="15">Itirapina</option> <option value="16">Itu</option> <option value="17">Jaboticabal</option> <option value="18">Jaú</option> <option value="19">Jundiaí</option> <option value="20">Limeira</option> <option value="21">matão</option> <option value="22">Mineiros do tiete</option> <option value="23">Osasco</option> <option value="24">Paulinia</option> <option value="25">Piracicaba</option> <option value="26">pirassununga</option> <option value="27">Porto Ferreira</option> <option value="28">Ribeirão Bonito</option> <option value="29">Ribeirão Preto</option> <option value="30">Rio Claro</option> <option value="31">Salto</option> <option value="32">Santa Bárbara D'Oeste</option> <option value="33">Santa Gertrudes</option> <option value="34">São Carlos</option> <option value="35">São Manuel</option> <option value="36">São Paulo</option> <option value="37">Sertãozinho</option> <option value="38">Tiete</option> <option value="39">Torrinha</h4></option> </select></td> </tr> <tr> <td></td> <td>Escolha uma cidade Destino</td> </tr> <tr> <td><h4>Para :</h4></td> <td><select name="rota_para"> <option value="1">Araçariguama</option> <option value="2">Araraquara</option> <option value="3">Araras</option> <option value="4">Barra Bonita</option> <option value="5">Barueri</option> <option value="6">Boa Esperança do Sul</option> <option value="7">Botucatu</option> <option value="8">Brotas</option> <option value="9">Campinas</option> <option value="10">Cordeirópolis</option> <option value="11">Dois córregos</option> <option value="12">Dourado</option> <option value="13">Hortolândia</option> <option value="14">Ibaté</option> <option value="15">Itirapina</option> <option value="16">Itu</option> <option value="17">Jaboticabal</option> <option value="18">Jaú</option> <option value="19">Jundiaí</option> <option value="20">Limeira</option> <option value="21">matão</option> <option value="22">Mineiros do tiete</option> <option value="23">Osasco</option> <option value="24">Paulinia</option> <option value="25">Piracicaba</option> <option value="26">pirassununga</option> <option value="27">Porto Ferreira</option> <option value="28">Ribeirão Bonito</option> <option value="29">Ribeirão Preto</option> <option value="30">Rio Claro</option> <option value="31">Salto</option> <option value="32">Santa Bárbara D'Oeste</option> <option value="33">Santa Gertrudes</option> <option value="34">São Carlos</option> <option value="35">São Manuel</option> <option value="36">São Paulo</option> <option value="37">Sertãozinho</option> <option value="38">Tiete</option> <option value="39">Torrinha</option> </select></td> </tr> <tr> <td></td> <td><input type=submit value="procurar Melhor Rota"></td> </tr> </form> </table> </div> </div> <div class="corpo_branco"> <br> <br> <br> <br> <br> <br> <br> </div> <footer> <br> <br> <h2 align="center"><font color="#FCFBFB">TRABALHO 1 - MENOR CAMINHO EM GRAFOS</font></h2> </footer> </body> </html> Resultado.php <!-- DISCIPLINA: GRAFOS E AUTÔMATOS --> <!doctype html> <html lang="pt-br"> <head> <link href='http://fonts.googleapis.com/css?family=Open+Sans:300,400,600,700' rel='stylesheet' type='text/css'> <link href='http://fonts.googleapis.com/css?family=Fjalla+One|Archivo+Narrow|Oswald:400,700' rel='stylesheet' type='text/css'> <link rel="stylesheet" href="css/reset.css" type="text/css" /> <link rel="stylesheet" href="css/style.css" type="text/css" /> <?php include("Dijkstra.php"); include("nome.php"); // I é a distância infinita. define('I',1000); // Tamanho da matriz $matrixWidth = 50; // $matriz é uma matriz no seguinte formato: (rota 1, rota 2, distância de aresta) $matriz = array( array("1", "5", 26,), array("1", "16", 51), array("2", "6", 35), array("2", "14", 29), array("2", "21", 33), array("3", "20", 25), array("3", "26", 24), array("4", "18", 25), array("4", "35", 35), array("5", "1", 26), array("5", "23", 12), array("6", "2", 35), array("6", "12", 27), array("6", "18", 42), array("7", "35", 26), array("7", "38", 95), array("8", "15", 35), array("8", "18", 56), array("8", "39", 21), array("9", "13", 20), array("9", "19", 38), array("9", "24", 23), array("9", "31", 42), array("10", "20", 18), array("10", "33", 10), array("11", "22", 12), array("11", "33", 10), array("12", "6", 27), array("12", "28", 19), array("13", "9", 20), array("13", "32", 34), array("14", "2", 29), array("14", "34", 15), array("15", "8", 35), array("15", "26", 56), array("15", "30", 42), array("15", "34", 36), array("16", "1", 51), array("16", "19", 48), array("16", "31", 59), array("16", "38", 57), array("17", "21", 45), array("17", "37", 41), array("18", "4", 25), array("18", "6", 42), array("18", "8", 56), array("18", "22", 20), array("19", "9", 38), array("19", "16", 48), array("19", "36", 59), array("20", "3", 25), array("20", "10", 18), array("20", "24", 45), array("20", "32", 24), array("21", "2", 33), array("21", "17", 45), array("22", "11", 12), array("22", "18", 20), array("23", "5", 12), array("23", "36", 23), array("24", "9", 23), array("24", "20", 45), array("25", "30", 40), array("25", "31", 70), array("25", "39", 87), array("26", "3", 44), array("26", "15", 56), array("26", "27", 24), array("27", "26", 24), array("27", "29", 88), array("27", "34", 57), array("28", "12", 19), array("28", "34", 51), array("29", "2", 89), array("29", "27", 88), array("29", "34", 101), array("29", "37", 21), array("30", "15", 42), array("30", "25", 40), array("30", "33", 8), array("31", "9", 42), array("31", "16", 59), array("31", "25", 70), array("32", "13", 34), array("32", "20", 34), array("33", "10", 10), array("33", "30", 8), array("34", "14", 15), array("34", "15", 36), array("34", "27", 57), array("34", "28", 51), array("34", "29", 101), array("35", "4", 35), array("35", "7", 26), array("36", "19", 59), array("36", "23", 23), array("37", "17", 41), array("37", "29", 21), array("38", "7", 95), array("38", "16", 57), array("39", "8", 21), array("39", "11", 29), array("39", "25", 87), ); $nossoMapa = array(); // Leia a $matriz e empurrá-los para o mapa for ($i=0,$m=count($matriz); $i<$m; $i++) { $x = $matriz[$i][0]; $y = $matriz[$i][1]; $c = $matriz[$i][2]; $nossoMapa[$x][$y] = $c; $nossoMapa[$y][$x] = $c; } // distância de um nó para si é sempre zero for ($i=0; $i < $matrixWidth; $i++) { for ($k=0; $k < $matrixWidth; $k++) { if ($i == $k) $nossoMapa[$i][$k] = 0; } } // Inicializa o algoritmo $dijkstra = new Dijkstra($nossoMapa, I,$matrixWidth); // $dijkstra->findShortestPath; para encontrar único caminho... $rota_de = $_POST['rota_de']; $rota_para = $_POST['rota_para']; $dijkstra->EncontrarCaminhoCurto($rota_de, $rota_para); //retorno das variaveis depois do algoritmo $array2 = $dijkstra -> PuxarResultado((int) $rota_para); $qtd_cidade = $array2["dados"]["caminho"]; $array3 = $array2["dados"]["lista"]; $lista = explode(" ", $array3); ?> </head> <title>GPS</title> <body onLoad="main ();"> <header><div class="header"> <section><br/> <h1 align="center">Trabalho Grafo</h1> </section> </div></header> <div class="corpo_branco"> <br> <br> <br> <br> </div> <div class="corpo"> <aside> <h3>Sistema GPS</h3> <ol> <li>Cidade Origem.</li> <li>Cidade a ser deslocado.</li> <li>OBSERVAÇÕES:</li> <li>Sistema feito em PHP</li> <li>Sistema com Lista Adjacente</li> <li>Sistema com algoritmo Dijkstra</li> </ol> </aside> <div class="tabela" align="center"> <h2 align="center">GPS</h2> <table> <tr> <td><h5>Caminho mais curto: </h5></td> <td><b>a partir da Cidade <h4><?PHP echo nome($rota_de) ?></h4> para <h4><?PHP echo nome($rota_para) ?></h4></b></td> </tr> <tr> <td><h5>Lista Adjacente: </h5></td> <td><b><?PHP for($i =0; $i < $qtd_cidade; $i++){ echo (" => ".nome($lista[$i])); } ?></b></td> </tr> <tr> <td><h5>KM TOTAL: </h5></td> <td><b><?PHP echo $array2["dados"]["km"] ?></b></td> </tr> <tr> <td><h5>Cidades percorridas: </h5></td> <td><b><?PHP echo $array2["dados"]["caminho"] ?></b></td> </tr> <tr> <td></td> <td><button><a href="index.php"><h4>voltar</h4></a></button></td> </tr> </table> </div> </div> <div class="corpo_branco"> <br> <br> <br> <br> <br> <br> <br> <br> <br> </div> <footer> <br> <br> <h2 align="center"><font color="#FCFBFB">TRABALHO 1 - MENOR CAMINHO EM GRAFOS</font></h2> </body> </html> Converter nome nome.php <?PHP function nome ($converter) { switch ($converter) { case "1": return "Araçariguama"; break; case "2": return "Araraquara"; break; case "3": return "Araras"; break; case "4": return "Barra Bonita"; break; case "5": return "Barueri"; break; case "6": return "Boa Esperança do Sul"; break; case "7": return "Botucatu"; break; case "8": return "Brotas"; break; case "9": return "Campinas"; break; case "10": return "Cordeirópolis"; break; case "11": return "Dois córregos"; break; case "12": return "Dourado"; break; case "13": return "Hortolândia"; break; case "14": return "Ibaté"; break; case "15": return "Itirapina"; break; case "16": return "Itu"; break; case "17": return "Jaboticabal"; break; case "18": return "Jaú"; break; case "19": return "Jundiaí"; break; case "20": return "Limeira"; break; case "21": return "matâo"; break; case "22": return "Mineiros do tiete"; break; case "23": return "Osasco"; break; case "24": return "Paulinia"; break; case "25": return "Piracicaba"; break; case "26": return "pirassununga"; break; case "27": return "Porto Ferreira"; break; case "28": return "Ribeirâo Bonito"; break; case "29": return "Ribeirâo Breto"; break; case "30": return "Rio Claro"; break; case "31": return "Salto"; break; case "32": return "Santa Bárbara D'Oeste"; break; case "33": return "Santa Gertrudes"; break; case "34": return "São Carlos"; break; case "35": return "São Manuel"; break; case "36": return "São Paulo"; break; case "37": return "Sertãozinho"; break; case "38": return "Tiete"; break; case "39": return "Torrinha"; break; } } ?> Algoritmo Dijstra Dijstra.php <?php class Dijkstra { var $visitado = array(); var $distancia = array(); var $No_anterior = array(); var $no_inicio =null; var $mapa = array(); var $distancia_infinita = 0; var $numero_de_nos = 0; var $melhor_caminho = 0; var $matrixWidth = 0; function Dijkstra(&$nossoMapa, $distancia_infinita) { $this -> distancia_infinita = $distancia_infinita; $this -> mapa = &$nossoMapa; $this -> numero_de_nos = count($nossoMapa); $this -> melhor_caminho = 0; } function EncontrarCaminhoCurto($de,$para) { $this -> no_inicio = $de; for ($i=0;$i<$this -> numero_de_nos;$i++) { if ($i == $this -> no_inicio) { $this -> visitado[$i] = true; $this -> distancia[$i] = 0; } else { $this -> visitado[$i] = false; $this -> distancia[$i] = isset($this -> mapa[$this -> no_inicio][$i]) ? $this -> mapa[$this -> no_inicio][$i] : $this -> distancia_infinita; } $this -> No_anterior[$i] = $this -> no_inicio; } $maxTentativa = $this -> numero_de_nos; $tentativa = 0; while (in_array(false,$this -> visitado,true) && $tentativa <= $maxTentativa) { $this -> melhor_caminho = $this->EncontrarMelhorCaminho($this->distancia,array_keys($this -> visitado,false,true)); if($para !== null && $this -> melhor_caminho === $para) { break; } $this -> atualizar_distancia($this -> melhor_caminho); $this -> visitado[$this -> melhor_caminho] = true; $tentativa++; } } function EncontrarMelhorCaminho($ourDistance, $ourNodesLeft) { $melhor_caminho = $this -> distancia_infinita; $melhor_no = 0; for ($i = 0,$m=count($ourNodesLeft); $i < $m; $i++) { if($ourDistance[$ourNodesLeft[$i]] < $melhor_caminho) { $melhor_caminho = $ourDistance[$ourNodesLeft[$i]]; $melhor_no = $ourNodesLeft[$i]; } } return $melhor_no; } function atualizar_distancia($obp) { for ($i=0;$i<$this -> numero_de_nos;$i++) { if( (isset($this->mapa[$obp][$i])) && (!($this->mapa[$obp][$i] == $this->distancia_infinita) || ($this->mapa[$obp][$i] == 0 )) && (($this->distancia[$obp] + $this->mapa[$obp][$i]) < $this -> distancia[$i]) ) { $this -> distancia[$i] = $this -> distancia[$obp] + $this -> mapa[$obp][$i]; $this -> No_anterior[$i] = $obp; } } } function printMap(&$mapa) { $placeholder = ' %' . strlen($this -> distancia_infinita) .'d'; $foo = ''; for($i=0,$im=count($mapa);$i<$im;$i++) { for ($k=0,$m=$im;$k<$m;$k++) { $foo.= sprintf($placeholder, isset($mapa[$i][$k]) ? $mapa[$i][$k] : $this -> distancia_infinita); } $foo.= "\n"; } return $foo; } function PuxarResultado($para) { $ourShortestPath = array(); $foo = ''; for ($i = 0; $i < $this -> numero_de_nos; $i++) { if($para !== null && $para !== $i) { continue; } $ourShortestPath[$i] = array(); $endNode = null; $currNode = $i; $ourShortestPath[$i][] = $i; while ($endNode === null || $endNode != $this -> no_inicio) { $ourShortestPath[$i][] = $this -> No_anterior[$currNode]; $endNode = $this -> No_anterior[$currNode]; $currNode = $this -> No_anterior[$currNode]; } $ourShortestPath[$i] = array_reverse($ourShortestPath[$i]); if ($para === null || $para === $i) { if($this -> distancia[$i] >= $this -> distancia_infinita) { $foo .= sprintf("Não a Rota entre (%d) e %d \n",$this -> startnode,$i); } else { $cidade_ida= $this -> no_inicio; $cidade_volta= $i; $discancia= $this -> distancia[$i]; $cidade_percorrida= count($ourShortestPath[$i]); $lista= implode(' ',$ourShortestPath[$i]); $foo = array ("dados" => array ("km" => $discancia, "caminho" => $cidade_percorrida, "lista" => $lista)); } } } return $foo; } } // end class ?>
  4. Caio Thimons Silva Arruda

    Algoritmo dijkstra menor distância

    Boa Tarde à todos, programa há um anos, porém estou com um problema na qual não sei como fazer, já procurei na net toda e principalmente aqui no iMasters, irei postar com mais detalhes: Estou fazendo um projeto da faculdade onde é buscar o menor caminho de uma rota, onde está sendo usado o algoritmo de Dijkstra, ele é formado em 2 páginas, index e resultado, o index o usuário pode colocar a cidade de origem e cidade de destino final, a página de resultado puxa a página do algoritmo, o projeto está funcionando corretamente, porém o Professor quer que eu puxo as cidades através de um arquivo .txt, já fiz alguns teste porém não funciona, irei posta as páginas: O Professor irá fornecer um arquivo .txt do seguinte modelo: São Paulo;Santos;100 O algoritmo funciona apenas com número, nesse modelo => ("1","2",100) Sendo 1 São Paulo e 2 Santos e 100 a distância de um para o outro. Precisa da ideia de alguém de como fazer essa conversão, já que não consegui mexer no algoritmo do Kijkstra para que aceita-se o nome da cidade, sendo que a array que ele aceita é("1","2",100); Alguém poderia me dar alguma ideia? , Agradeço deis de já Index: <!-- DISCIPLINA: GRAFOS E AUTÔMATOS --> <!doctype html> <html lang="pt-br"> <head> <link href='http://fonts.googleapis.com/css?family=Open+Sans:300,400,600,700' rel='stylesheet' type='text/css'> <link href='http://fonts.googleapis.com/css?family=Fjalla+One|Archivo+Narrow|Oswald:400,700' rel='stylesheet' type='text/css'> <link rel="stylesheet" href="css/reset.css" type="text/css" /> <link rel="stylesheet" href="css/style.css" type="text/css" /> </head> <title>GPS</title> <body> <header><div class="header"> <section><br/> <h1 align="center">Trabalho Grafo</h1> </section> </div></header> <div class="corpo_branco"> <br> <br> <br> <br> </div> <div class="corpo"> <aside> <h3>Sistema GPS</h3> <ol> <li>Cidade Origem.</li> <li>Cidade a ser deslocado.</li> <li>OBSERVAÇÕES:</li> <li>Sistema feito em PHP</li> <li>Sistema com Lista Adjacente</li> <li>Sistema com algoritmo Dijkstra</li> </ol> </aside> <div class="tabela" align="center"> <h2 align="center">GPS</h2> <table> <form name="form" action="resultado.php" method="post"> <tr> <td></td> <td>Informe a cidade local</td> </tr> <tr> <td><h4>Iniciar de :</h4></td> <td><select name="rota_de"> <option value="1"><h4>Araçariguama</option> <option value="2">Araraquara</option> <option value="3">Araras</option> <option value="4">Barra Bonita</option> <option value="5">Barueri</option> <option value="6">Boa Esperança do Sul</option> <option value="7">Botucatu</option> <option value="8">Brotas</option> <option value="9">Campinas</option> <option value="10">Cordeirópolis</option> <option value="11">Dois córregos</option> <option value="12">Dourado</option> <option value="13">Hortolândia</option> <option value="14">Ibaté</option> <option value="15">Itirapina</option> <option value="16">Itu</option> <option value="17">Jaboticabal</option> <option value="18">Jaú</option> <option value="19">Jundiaí</option> <option value="20">Limeira</option> <option value="21">matão</option> <option value="22">Mineiros do tiete</option> <option value="23">Osasco</option> <option value="24">Paulinia</option> <option value="25">Piracicaba</option> <option value="26">pirassununga</option> <option value="27">Porto Ferreira</option> <option value="28">Ribeirão Bonito</option> <option value="29">Ribeirão Preto</option> <option value="30">Rio Claro</option> <option value="31">Salto</option> <option value="32">Santa Bárbara D'Oeste</option> <option value="33">Santa Gertrudes</option> <option value="34">São Carlos</option> <option value="35">São Manuel</option> <option value="36">São Paulo</option> <option value="37">Sertãozinho</option> <option value="38">Tiete</option> <option value="39">Torrinha</h4></option> </select></td> </tr> <tr> <td></td> <td>Escolha uma cidade Destino</td> </tr> <tr> <td><h4>Para :</h4></td> <td><select name="rota_para"> <option value="1">Araçariguama</option> <option value="2">Araraquara</option> <option value="3">Araras</option> <option value="4">Barra Bonita</option> <option value="5">Barueri</option> <option value="6">Boa Esperança do Sul</option> <option value="7">Botucatu</option> <option value="8">Brotas</option> <option value="9">Campinas</option> <option value="10">Cordeirópolis</option> <option value="11">Dois córregos</option> <option value="12">Dourado</option> <option value="13">Hortolândia</option> <option value="14">Ibaté</option> <option value="15">Itirapina</option> <option value="16">Itu</option> <option value="17">Jaboticabal</option> <option value="18">Jaú</option> <option value="19">Jundiaí</option> <option value="20">Limeira</option> <option value="21">matão</option> <option value="22">Mineiros do tiete</option> <option value="23">Osasco</option> <option value="24">Paulinia</option> <option value="25">Piracicaba</option> <option value="26">pirassununga</option> <option value="27">Porto Ferreira</option> <option value="28">Ribeirão Bonito</option> <option value="29">Ribeirão Preto</option> <option value="30">Rio Claro</option> <option value="31">Salto</option> <option value="32">Santa Bárbara D'Oeste</option> <option value="33">Santa Gertrudes</option> <option value="34">São Carlos</option> <option value="35">São Manuel</option> <option value="36">São Paulo</option> <option value="37">Sertãozinho</option> <option value="38">Tiete</option> <option value="39">Torrinha</option> </select></td> </tr> <tr> <td></td> <td><input type=submit value="procurar Melhor Rota"></td> </tr> </form> </table> </div> </div> <div class="corpo_branco"> <br> <br> <br> <br> <br> <br> <br> </div> <footer> <br> <br> <h2 align="center"><font color="#FCFBFB">TRABALHO 1 - MENOR CAMINHO EM GRAFOS</font></h2> </footer> </body> </html> Resultado.php <!-- DISCIPLINA: GRAFOS E AUTÔMATOS --> <!doctype html> <html lang="pt-br"> <head> <link href='http://fonts.googleapis.com/css?family=Open+Sans:300,400,600,700' rel='stylesheet' type='text/css'> <link href='http://fonts.googleapis.com/css?family=Fjalla+One|Archivo+Narrow|Oswald:400,700' rel='stylesheet' type='text/css'> <link rel="stylesheet" href="css/reset.css" type="text/css" /> <link rel="stylesheet" href="css/style.css" type="text/css" /> <?php include("Dijkstra.php"); include("nome.php"); // I é a distância infinita. define('I',1000); // Tamanho da matriz $matrixWidth = 50; // $matriz é uma matriz no seguinte formato: (rota 1, rota 2, distância de aresta) $matriz = array( array("1", "5", 26,), array("1", "16", 51), array("2", "6", 35), array("2", "14", 29), array("2", "21", 33), array("3", "20", 25), array("3", "26", 24), array("4", "18", 25), array("4", "35", 35), array("5", "1", 26), array("5", "23", 12), array("6", "2", 35), array("6", "12", 27), array("6", "18", 42), array("7", "35", 26), array("7", "38", 95), array("8", "15", 35), array("8", "18", 56), array("8", "39", 21), array("9", "13", 20), array("9", "19", 38), array("9", "24", 23), array("9", "31", 42), array("10", "20", 18), array("10", "33", 10), array("11", "22", 12), array("11", "33", 10), array("12", "6", 27), array("12", "28", 19), array("13", "9", 20), array("13", "32", 34), array("14", "2", 29), array("14", "34", 15), array("15", "8", 35), array("15", "26", 56), array("15", "30", 42), array("15", "34", 36), array("16", "1", 51), array("16", "19", 48), array("16", "31", 59), array("16", "38", 57), array("17", "21", 45), array("17", "37", 41), array("18", "4", 25), array("18", "6", 42), array("18", "8", 56), array("18", "22", 20), array("19", "9", 38), array("19", "16", 48), array("19", "36", 59), array("20", "3", 25), array("20", "10", 18), array("20", "24", 45), array("20", "32", 24), array("21", "2", 33), array("21", "17", 45), array("22", "11", 12), array("22", "18", 20), array("23", "5", 12), array("23", "36", 23), array("24", "9", 23), array("24", "20", 45), array("25", "30", 40), array("25", "31", 70), array("25", "39", 87), array("26", "3", 44), array("26", "15", 56), array("26", "27", 24), array("27", "26", 24), array("27", "29", 88), array("27", "34", 57), array("28", "12", 19), array("28", "34", 51), array("29", "2", 89), array("29", "27", 88), array("29", "34", 101), array("29", "37", 21), array("30", "15", 42), array("30", "25", 40), array("30", "33", 8), array("31", "9", 42), array("31", "16", 59), array("31", "25", 70), array("32", "13", 34), array("32", "20", 34), array("33", "10", 10), array("33", "30", 8), array("34", "14", 15), array("34", "15", 36), array("34", "27", 57), array("34", "28", 51), array("34", "29", 101), array("35", "4", 35), array("35", "7", 26), array("36", "19", 59), array("36", "23", 23), array("37", "17", 41), array("37", "29", 21), array("38", "7", 95), array("38", "16", 57), array("39", "8", 21), array("39", "11", 29), array("39", "25", 87), ); $nossoMapa = array(); // Leia a $matriz e empurrá-los para o mapa for ($i=0,$m=count($matriz); $i<$m; $i++) { $x = $matriz[$i][0]; $y = $matriz[$i][1]; $c = $matriz[$i][2]; $nossoMapa[$x][$y] = $c; $nossoMapa[$y][$x] = $c; } // distância de um nó para si é sempre zero for ($i=0; $i < $matrixWidth; $i++) { for ($k=0; $k < $matrixWidth; $k++) { if ($i == $k) $nossoMapa[$i][$k] = 0; } } // Inicializa o algoritmo $dijkstra = new Dijkstra($nossoMapa, I,$matrixWidth); // $dijkstra->findShortestPath; para encontrar único caminho... $rota_de = $_POST['rota_de']; $rota_para = $_POST['rota_para']; $dijkstra->EncontrarCaminhoCurto($rota_de, $rota_para); //retorno das variaveis depois do algoritmo $array2 = $dijkstra -> PuxarResultado((int) $rota_para); $qtd_cidade = $array2["dados"]["caminho"]; $array3 = $array2["dados"]["lista"]; $lista = explode(" ", $array3); ?> </head> <title>GPS</title> <body onLoad="main ();"> <header><div class="header"> <section><br/> <h1 align="center">Trabalho Grafo</h1> </section> </div></header> <div class="corpo_branco"> <br> <br> <br> <br> </div> <div class="corpo"> <aside> <h3>Sistema GPS</h3> <ol> <li>Cidade Origem.</li> <li>Cidade a ser deslocado.</li> <li>OBSERVAÇÕES:</li> <li>Sistema feito em PHP</li> <li>Sistema com Lista Adjacente</li> <li>Sistema com algoritmo Dijkstra</li> </ol> </aside> <div class="tabela" align="center"> <h2 align="center">GPS</h2> <table> <tr> <td><h5>Caminho mais curto: </h5></td> <td><b>a partir da Cidade <h4><?PHP echo nome($rota_de) ?></h4> para <h4><?PHP echo nome($rota_para) ?></h4></b></td> </tr> <tr> <td><h5>Lista Adjacente: </h5></td> <td><b><?PHP for($i =0; $i < $qtd_cidade; $i++){ echo (" => ".nome($lista[$i])); } ?></b></td> </tr> <tr> <td><h5>KM TOTAL: </h5></td> <td><b><?PHP echo $array2["dados"]["km"] ?></b></td> </tr> <tr> <td><h5>Cidades percorridas: </h5></td> <td><b><?PHP echo $array2["dados"]["caminho"] ?></b></td> </tr> <tr> <td></td> <td><button><a href="index.php"><h4>voltar</h4></a></button></td> </tr> </table> </div> </div> <div class="corpo_branco"> <br> <br> <br> <br> <br> <br> <br> <br> <br> </div> <footer> <br> <br> <h2 align="center"><font color="#FCFBFB">TRABALHO 1 - MENOR CAMINHO EM GRAFOS</font></h2> </body> </html> Converter nome nome.php <?PHP function nome ($converter) { switch ($converter) { case "1": return "Araçariguama"; break; case "2": return "Araraquara"; break; case "3": return "Araras"; break; case "4": return "Barra Bonita"; break; case "5": return "Barueri"; break; case "6": return "Boa Esperança do Sul"; break; case "7": return "Botucatu"; break; case "8": return "Brotas"; break; case "9": return "Campinas"; break; case "10": return "Cordeirópolis"; break; case "11": return "Dois córregos"; break; case "12": return "Dourado"; break; case "13": return "Hortolândia"; break; case "14": return "Ibaté"; break; case "15": return "Itirapina"; break; case "16": return "Itu"; break; case "17": return "Jaboticabal"; break; case "18": return "Jaú"; break; case "19": return "Jundiaí"; break; case "20": return "Limeira"; break; case "21": return "matâo"; break; case "22": return "Mineiros do tiete"; break; case "23": return "Osasco"; break; case "24": return "Paulinia"; break; case "25": return "Piracicaba"; break; case "26": return "pirassununga"; break; case "27": return "Porto Ferreira"; break; case "28": return "Ribeirâo Bonito"; break; case "29": return "Ribeirâo Breto"; break; case "30": return "Rio Claro"; break; case "31": return "Salto"; break; case "32": return "Santa Bárbara D'Oeste"; break; case "33": return "Santa Gertrudes"; break; case "34": return "São Carlos"; break; case "35": return "São Manuel"; break; case "36": return "São Paulo"; break; case "37": return "Sertãozinho"; break; case "38": return "Tiete"; break; case "39": return "Torrinha"; break; } } ?> Algoritmo Dijstra Dijstra.php <?php class Dijkstra { var $visitado = array(); var $distancia = array(); var $No_anterior = array(); var $no_inicio =null; var $mapa = array(); var $distancia_infinita = 0; var $numero_de_nos = 0; var $melhor_caminho = 0; var $matrixWidth = 0; function Dijkstra(&$nossoMapa, $distancia_infinita) { $this -> distancia_infinita = $distancia_infinita; $this -> mapa = &$nossoMapa; $this -> numero_de_nos = count($nossoMapa); $this -> melhor_caminho = 0; } function EncontrarCaminhoCurto($de,$para) { $this -> no_inicio = $de; for ($i=0;$i<$this -> numero_de_nos;$i++) { if ($i == $this -> no_inicio) { $this -> visitado[$i] = true; $this -> distancia[$i] = 0; } else { $this -> visitado[$i] = false; $this -> distancia[$i] = isset($this -> mapa[$this -> no_inicio][$i]) ? $this -> mapa[$this -> no_inicio][$i] : $this -> distancia_infinita; } $this -> No_anterior[$i] = $this -> no_inicio; } $maxTentativa = $this -> numero_de_nos; $tentativa = 0; while (in_array(false,$this -> visitado,true) && $tentativa <= $maxTentativa) { $this -> melhor_caminho = $this->EncontrarMelhorCaminho($this->distancia,array_keys($this -> visitado,false,true)); if($para !== null && $this -> melhor_caminho === $para) { break; } $this -> atualizar_distancia($this -> melhor_caminho); $this -> visitado[$this -> melhor_caminho] = true; $tentativa++; } } function EncontrarMelhorCaminho($ourDistance, $ourNodesLeft) { $melhor_caminho = $this -> distancia_infinita; $melhor_no = 0; for ($i = 0,$m=count($ourNodesLeft); $i < $m; $i++) { if($ourDistance[$ourNodesLeft[$i]] < $melhor_caminho) { $melhor_caminho = $ourDistance[$ourNodesLeft[$i]]; $melhor_no = $ourNodesLeft[$i]; } } return $melhor_no; } function atualizar_distancia($obp) { for ($i=0;$i<$this -> numero_de_nos;$i++) { if( (isset($this->mapa[$obp][$i])) && (!($this->mapa[$obp][$i] == $this->distancia_infinita) || ($this->mapa[$obp][$i] == 0 )) && (($this->distancia[$obp] + $this->mapa[$obp][$i]) < $this -> distancia[$i]) ) { $this -> distancia[$i] = $this -> distancia[$obp] + $this -> mapa[$obp][$i]; $this -> No_anterior[$i] = $obp; } } } function printMap(&$mapa) { $placeholder = ' %' . strlen($this -> distancia_infinita) .'d'; $foo = ''; for($i=0,$im=count($mapa);$i<$im;$i++) { for ($k=0,$m=$im;$k<$m;$k++) { $foo.= sprintf($placeholder, isset($mapa[$i][$k]) ? $mapa[$i][$k] : $this -> distancia_infinita); } $foo.= "\n"; } return $foo; } function PuxarResultado($para) { $ourShortestPath = array(); $foo = ''; for ($i = 0; $i < $this -> numero_de_nos; $i++) { if($para !== null && $para !== $i) { continue; } $ourShortestPath[$i] = array(); $endNode = null; $currNode = $i; $ourShortestPath[$i][] = $i; while ($endNode === null || $endNode != $this -> no_inicio) { $ourShortestPath[$i][] = $this -> No_anterior[$currNode]; $endNode = $this -> No_anterior[$currNode]; $currNode = $this -> No_anterior[$currNode]; } $ourShortestPath[$i] = array_reverse($ourShortestPath[$i]); if ($para === null || $para === $i) { if($this -> distancia[$i] >= $this -> distancia_infinita) { $foo .= sprintf("Não a Rota entre (%d) e %d \n",$this -> startnode,$i); } else { $cidade_ida= $this -> no_inicio; $cidade_volta= $i; $discancia= $this -> distancia[$i]; $cidade_percorrida= count($ourShortestPath[$i]); $lista= implode(' ',$ourShortestPath[$i]); $foo = array ("dados" => array ("km" => $discancia, "caminho" => $cidade_percorrida, "lista" => $lista)); } } } return $foo; } } // end class ?>
×

Important Information

Ao usar o fórum, você concorda com nossos Terms of Use.