A EFICIÊNCIA POLIONOMIAL DO SIMPLEX PARA REDES: Aplicação em um problema do caminho mais curto

Abstract

Neste trabalho é apresentado um algoritmo simplex para rede de complexidade O(nm) que encontra uma árvore de caminhos mais curtos, de um nó para todos os outros nós em uma rede direcionada, de n nós e m arcos, ou encontra um ciclo negativo. O tempo de execução desse algoritmo, no pior caso, é tão rápido quanto qualquer algoritmo polinomial que resolva este problema.

Keywords

• Algoritmo simplex para redes. Complexidade. Árvores de busca.