Algoritmo dijkstra menor distância

Caio Thimons Silva Arruda · Abril 19, 2015

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

Criquio · Abril 19, 2015

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

Caio Thimons Silva Arruda · Abril 20, 2015

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

MoiDVAec · Março 23, 2019

Bom dia, Caio!

Você tem esse algoritmo completo, com o mapa! Estou precisando para um trabalho da faculdade!

Motta · Março 23, 2019

Dicionário de algoritmos.

Entrar

Arquivado

Algoritmo dijkstra menor distância

Recommended Posts

Caio Thimons Silva Arruda 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

Criquio 19

Compartilhar este post

Link para o post

Compartilhar em outros sites

Caio Thimons Silva Arruda 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

MoiDVAec 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

Motta 645

Compartilhar este post

Link para o post

Compartilhar em outros sites

Javascript - Calcular Valores Monetário em Tempo Real

JavaScript - Exibir logo dentro da Tabela html

PHP+Codeigniter - Implementar o Input CÓDIGO ou ID do Produto

Este projeto é apoiado pelas empresas

Fóruns

Tempo Real

Informação importante