Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Dijkstra, Algoritmos Menor Caminho - Coggle Diagram
Algoritmo de Dijkstra
Caracteristicas
Grafo ponderado
Pesos não negativos
solução do problema do caminho mais curto
tempo computacional -> (O(E+V\log(V))
V = Vértices do grafo
E = Arestas do grafo
Funcionamento
encontre o nó mais próximo de V(ele mesmo)
enquanto houver nós não visitados
escolha o nó U com menor distância
para cada vizinho X de U cálcule a distância de V para X e depois de X para U
é menor?
Sim
Passe pelo caminho encontrado (V->X->U)
Não
Vá de V para U
mantenha um conjunto de nós não visitados
sequencia de passos
expandem uma solução parcial
Viabilidade
otimização
melhor solução dentre um conjunto próximo limitado (não necessariamente a melhor de todas as possíveis)
Irrevogável
Algoritmos Menor Caminho
Algoritmo de Floyd-Warshall
encontra o menor caminho entre todos os pares de vértices de um grafo
grafos
pode ser usado em um grafo com pesos negativos
sem ciclos negativos (soma das arestas negativa)
ponderado
Orientado
O valor do caminho entre 2 vértices é a soma de todas as arestas ao longo do caminho
funcionamento
inicializar matriz-distância
se i==j, a distância entre i e j é 0
Um nó para ele mesmo
existe aresta?
Sim
Distancia[i][j] = peso(i.j)
Não
Distancia[i][j] = infinito
para cada vértice(i,j), atualize a menor distância
Complexidade O(n³)
Algoritmo de Bellman-Ford
Digrafos ponderados
Pode ter peso negativo
Permite ciclos negativos
Mais lento que o Dijkstra
Resolve o problema de pesos negativos
Complexidade O(V x E)
Processa todas as arestas |V-1| vezes
se ao fim da iteração (k=|V -1|) for possível melhorar alguma distância
Há um ciclo negativo