Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmos de Grafos: Caminho Mais Curto com Fonte Simples, Algoritmo de…

- - - - O Caminho Mais Curto com Fonte Simples é um conceito na teoria dos grafos
      - caminho minimo é dado por:
        
        delta(u, v) = { w(p): u ~> v }
        
        se não houver caminha é infinito
  - - - Olha todos os pontos
      - Solução otima
      - quando dividir pra conquistar não é viável
    - - Melhor escolha do momento
      - Verificação local
- - - - se exister um loop com peso negativo
      - Em geral alg. requerem uma função admissível (sem custo negativo).
    - - Em ciclos negativos não é garantido encontrar a solução ótima.
      - Casos de caminho minimo = -∞ :warning:
        
        Soma do percurso < 0
        
        Se da fonte der pra alcançar um ciclo de peso negativo:
        
        Se um vértice for alcançado de outro curso peso é -∞
      - Apenas ciclos com peso 0 é permitido :check:
- - - - v.d > u.d + w (u, v)