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

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.