Um Algoritmo Dinâmico para Árvore de Caminhos Minimos

Propõe-se um algoritmo dinâmico para manter a árvore com raiz em um vértice especial origem e formada por caminhos m{\'{\i}}nimos para cada vértice do grafo. O grafo apresenta custo nas arestas e não apresenta restrições adicionais quanto ao dom{\'{\i}}nio do custo, desde que os valores não sejam negativos. Aborda-se o problema com múltiplas operações simultâneas sobre o grafo: aumento e diminuição de custo das arestas. Sua complexidade no pior caso é O(m + n log n) para um grafo com n vértices e m arestas. O tempo de execução é menor ou igaul à computação de uma nova árvore de caminhos m{\'{\i}}nimos. As operações sobre grafo são tratada por um único modelo, similiar ao algoritmo de Dijkstra.

2007