Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa Mental 12 - Coggle Diagram
Mapa Mental 12
Capítulo 8: "
Dynamic Programming
".
Seção 8.4: "
Warshall's and Floyd's Algorithms
".
Tópico: "
.Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem
".
Aqui será abordado o
problema dos caminhos mais curtos de todos os pares
.
Como o nome sugere, esse problema pede para encontrar os caminhos mais curtos de cada vértice para todos os outros em um
grafo conexo e com peso
.
Essa variação dos problemas de caminho mais curto foi muito estudada por ter importantes aplicações, como em comunicações, redes de transporte e pesquisas operacionais.
E uma de suas aplicações recentes é o pré-cálculo de distâncias para planejamento de movimento em jogos de computador.
É conveniente armazenar os comprimentos dos caminhos mais curtos em uma matriz \(n \times n \ \ D\) chamada matriz de distância.
O elemento \(d_{ij}\), que está nas i-ésima linha e j-ésima coluna, representa o comprimento do caminho mais curto do i-ésimo vértice ao j-ésimo vértice.
1 more item...