Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 12 - Coggle Diagram

- - - - Melhor para grafos densos
    - - Melhor para grafos esparsos
  - - - A partir da fonte (visitada), o algoritmo define o menor caminho para seus vértices adjecentes (não-visitados), e irá seguir para o vértice que lhe pesará menos
        
        Nisso a fonte se tornará o pai do vértice que está sendo visitado no momento
        
        Nessa passagem, esse vértice adjecente escolhido será marcado como visitado
        
        O vértice adjecente que foi escolhido é definido por meio de uma heap mínima
        
        Todos os vértices adjecentes e seus pesos são adicionados na heap e depois o vértice da raiz é escolhido
        
        Ao realizar o mesmo processo feito no vértice pai (nesse caso, a fonte s), o algoritmo irá comparar se a distância entre v e cada um de seus vértices adjecentes (D(v,x)) é maior ou não que a distância entre s e esses mesmos vértices (D(s,x))
        
        v = vértice que está sendo visitado no momento
        
        Se a distância D(v,x) for menor que D(s,x), então tudo continua igual
        
        Após isso o processo se repete; o vértice é definido como visitado e o algoritmo escolhe o próximo vértice para visitar via fila de prioridade, e assim por diante, até achar a menor distância para cada um dos vértices
        
        Se D(v,x) for maior que D(s,x), então a nova distância D(v,x) será a de D(s,x)
        
        Vértices que não são adjecentes tem a distância igual a ∞, ou seja um número extremamente grande, ou só um símbolo mesmo