Teoria dos Grafos - Djistrack
Por: eduardamaia17 • 25/9/2018 • 906 Palavras (4 Páginas) • 312 Visualizações
...
arcos de comprimento positivo já que negativos não apresentam exatidão e contem inutilidade diante do proposto. São calculadas e comparadas as distâncias do nó de origem, ou seja, a escola da estudante, para todas as possibilidades disponíveis até obter um resultado, isto é chegar em sua casa (Arenales, 2007).
As arestas podem conter um elemento conhecido como peso, equivalente na atividade a velocidade do percurso, que impactam nesse estudo, de forma que cada caminho terá valores distintos atribuídos e estes serão incluídos no cálculo modificando resultados (Sedgewick, 2002).
De acordo com Arenales, 2007, o tempo de execução do algoritmo de Dijkstra com m arestas (ruas) e com n vértices (esquinas) pode ser apresentado por O([m+n]log n.
Análise do algoritmo Dijstrack
No código abaixo está contido o inicio da classe com as variáveis privadas que serão utilizadas, para realizar as manipulações, comparações, definições de posições e resultados lógicos.
picture alt
Na imagem abaixo são apresentadas três classes.
A primeira tem como função a conversão de variáveis privadas em públicas, a segunda classe é formada por um acumulador que recolhe e armazena em si os valores das arestas (ruas) calculadas.
picture alt
A última classe, exibida a seguir, inicia o Algoritmo.
picture alt
Para compreensão do algoritmo é necessário relacionar que os vértices representam as esquinas e as arestas são as ruas.
O algoritmo é iniciado com um número finito para estabelecimento de limites.
A lógica ao percorrer as esquinas são etiquetadas e salvas, para realização de análise se o caminho selecionado é mais curto em relação às opções disponíveis.
As alternativas verificadas e determinadas como adequadas, transformam-se em um caminho visitado, sendo salvo em memória o nome da aresta.
picture alt picture alt
O processo se repete até que é encontrado o menor percurso.
Conforme são realizadas alterações das vias no decorrer dos anos, o algoritmo se adapta recalculando e comparando já que na presença de um caminho mais curto, este é selecionado e exibido em uma próxima pesquisa.
picture alt
Ao final de cada consulta o resultado do caminho inferior é exibido juntamente com os vértices que devem ser seguidos no percurso, como destacado acima em verde.
...