Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de Caminho Mínimo - Coggle Diagram
Algoritmos de Caminho Mínimo
Problema fundamental em teoria dos grafos.
Tipos de Grafos Envolvidos:
Direcionados vs. Não Direcionados.
Ponderados (com pesos nas arestas).
Arestas com pesos não negativos (importante para Dijkstra).
Algoritmo de Dijkstra
Encontra o caminho mínimo de um único nó de origem para todos os outros nós em um grafo.
Funciona apenas com pesos de arestas não negativos.
Estruturas de Dados Utilizadas
Array/Dicionário para armazenar as distâncias atuais.
Array/Dicionário para armazenar os predecessores (para reconstruir o caminho).
Fila de Prioridade (Min-Heap): essencial para selecionar eficientemente o próximo nó com a menor distância.
Complexidade de Tempo
Com array simples (ineficiente para grafos grandes): O(V^2)
Com Min-Heap: O((V+E)logV) (onde V = número de vértices, E = número de arestas).
Vantagens
Eficiente para grafos esparsos com pesos não negativos.
Amplamente utilizado.
Desvantagens
Não funciona com pesos negativos de arestas.
Floyd-Warshall
Encontra os caminhos mais curtos entre todos os pares possíveis de nós no grafo.
Principal Característica: Lida com pesos negativos de arestas (mas não com ciclos negativos).
Algoritmo de todos os pares de caminhos mínimos.
Vantagens
Lida com pesos negativos de arestas (se não houver ciclos negativos).
Encontra caminhos mínimos para todos os pares de nós.
Desvantagens
Complexidade de Tempo: O(V^3)
Mais lento para grafos grandes.
Não lida corretamente com a presença de ciclos negativos (pode retornar valores incorretos).
Objetivo: encontrar o caminho com menor "custo" (distância, tempo, etc.) entre dois nós.
Aplicações Comuns:
Redes de computadores (roteamento de pacotes).
Inteligência Artificial (planejamento de movimento).
GPS e navegação (rotas mais rápidas/curtas).
Logística e transporte.
Bellman-Ford
Encontra o caminho mais curto de um nó inicial específico para todos os outros nós no grafo.
Algoritmo de caminho mínimo de fonte única.
Principal Característica: Lida com arestas de peso negativo.
Vantagens
Capacidade de lidar com pesos negativos de arestas.
Detecta ciclos negativos.
Desvantagens
Complexidade de Tempo: O(V⋅E) (V = vértices, E = arestas).
Mais lento que Dijkstra.