Mapa Mental - Algoritmos Grafos

Prévia do material em texto

Grafos Ponderados Algoritmo de Bellman-Ford Arestas associadas a pesos Calcula caminho mínimo de um nó para que representam distâncias todos outros nós ou custos Permite pesos negativos nas arestas Pesos podem indicar tempos, do grafo custos ou outras medidas Executa sucessivas iterações até relevantes comprimento máximo n-1 Esses pesos são essenciais Útil para detectar ciclos negativos para cálculo de caminhos em grafos ponderados mínimos Permitem modelar problemas reais como rotas e redes de comunicação Algoritmos Algoritmo de Kruskal Algoritmo de Floyd-Warshall Ordena todas as arestas do grafo por peso crescente Grafos Calcula todos menores caminhos entre todos OS pares de nós Verifica se a inclusão da Utiliza matriz de adjacência aresta gera ciclo na árvore modificada para armazenar distâncias Adiciona arestas que não Complexidade temporal é devido formam ciclos para construir a três laços aninhados árvore Suporta grafos com pesos negativos, Idealizado por Joseph Kruskal sem ciclos negativos para árvores geradoras mínimas Iterações e Seleção de Nós Em cada iteração, seleciona-se nó com menor distância ainda livre Atualizam-se distâncias dos nós Algoritmo de Dijkstra adjacentes ao nó selecionado Vetores em Algoritmos de Caminho Encontra caminho mínimo de um Processo continua até todos OS nós Vetor distância armazena menor custo nó inicial para demais serem incluídos no conjunto IN conhecido até cada nó Inicializa conjunto IN com nó Permite determinar caminho mínimo Vetor antecessor registra nó anterior no de origem do caminho entre origem e destino caminho mínimo Seleciona nó de menor Ambos são atualizados a cada iteração do distância ainda não incluído algoritmo Atualiza vetores de distância e Esses vetores permitem reconstruir antecessores a cada iteração caminho final encontrado