Voltar
Artigo Acesso aberto Revisado por pares
BIBTEX RIS

A eficiência Polionomial do simplex para redes: Aplicação em um problema do caminho mais curto

2003; Essentia Editora; Volume: 5; Issue: 2 Linguagem: Português

10.5935/1809-2667.20030015

ISSN

1809-2667

Autores

Carlos Eduardo Varejão Marinho, Antonio José dos Santos Neto,

Tópico(s)

Advanced Graph Theory Research

Resumo

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.

Referência(s)