Djakstra

´ TRABALHO PRATICO 1: Labirinto Marini Almeida Nascimento 1 Departamento de Matem´ tica e Ciencia da computacao a ¸˜ - Universidade Federal de Minas Gerais (UFMG) marinini.almeida@gmail.com Resumo. Implementar um programa em linguagem C capaz de fazer um rato percorrer um labirinto e encontrar a sa´da. ı 1. INTRODUCAO ¸˜ ´ O problema em estudo neste projeto e o problema de deslocamento no plano bidimensional, onde queremos determinar um caminho entre duas coordenadas. ` Este problema de deslocamento n˜ o e aplic´ vel somente a jogos. Podemos pensar a ´ a tamb´ m em um programa usado no GPS -sistema de posicionamento global- ,por exeme plo, para determinar o trajeto de um carro. Nesse trabalho ser´ determinado o caminho percorrido no plano em de certo rato a at´ encontrar a saida do labirinto. e 2. IMPLEMENTACAO ¸˜ Achar um caminho entre dois pontos quaisquer neste grafo basta testar todas as possibilidades. Entretanto, esta abordagem (conhecida como m´ todo de forca bruta) traz alguns e ¸ ´ bastante demorada e n˜ o garante que o caminho mais curto (ou com incovenientes: E a menor custo) seja encontrado. Por isso a ultilizacao de um algoritmo que ache o caminho mais curto seria con¸˜ veniente. Para podermos usar essa abordagem, decidimos interpretar o labirinto do projeto ´ como um grafo, onde cada caracter e um vertice do grafo e dois caracteres adjacentes diferentes de 1 formam uma aresta entre eles. Para a resolucao desse projeto foi usado o…