Please enable JavaScript.
Coggle requires JavaScript to display documents.
INICIO - Coggle Diagram
INICIO
Djkstra
-
Aplicabilidade
Funciona para grafos direcionados e não direcionados, desde que os pesos das arestas sejam não negativos
Abordagem Greedy
O algoritmo é um exemplo da técnica gulosa (greedy). Ele encontra os caminhos mais curtos em ordem crescente de distância a partir da fonte
Funcionamento Geral
Mantém um conjunto VT de vértices para os quais o caminho mais curto já foi encontrado. Inicialmente, VT contém apenas a fonte.
A cada passo, o algoritmo adiciona a VT o vértice u (fora de VT) que está mais próximo da fonte. A "proximidade" é medida como a soma da distância até um vértice v já em VT mais o peso da aresta (v, u).
Para facilitar, cada vértice u é rotulado com du (o comprimento do caminho mais curto encontrado até agora da fonte para u) e pu (o vértice que precede u nesse caminho).
O algoritmo usa uma fila de prioridade Q para armazenar os vértices "fronteiriços" (fora de VT mas adjacentes a algum vértice em VT), priorizados pelo seu valor d.
-
Floyd’s Algorithm
A Ideia Central
algoritmo constrói a matriz de distâncias através de uma série de matrizes n x n: D(0), D(1), ..., D(k-1), D(k), ..., D(n).
Cada matriz D(k) contém os comprimentos dos caminhos mais curtos entre todos os pares de vértices (i, j), com a restrição de que todos os vértices intermediários nesses caminhos devem ter um número (índice) não maior que k.
-
D(n) é a matriz de distâncias final, pois permite que todos os vértices (1 a n) sejam usados como intermediários.
-
Eficiência
O algoritmo possui três loops aninhados, cada um executando n vezes.
Portanto, a eficiência de tempo é cúbica: Θ(n³)
A eficiência de espaço também é quadrática, Θ(n²), para armazenar a matriz.