Jump to content
Caio Thimons Silva Arruda

Algoritmo dijkstra menor distância

Recommended Posts

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 
?>

Share this post


Link to post
Share on other sites

Os values das options são os números certos de cada cidade? Se for, é só pesquisar eles no arquivo texto.

Share this post


Link to post
Share on other sites

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;
?>

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

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