Open AccessA eficiência Polionomial do simplex para redes: Aplicação em um problema do caminho mais curto
Author(s) -
Carlos Eduardo Varejão Marinho,
Antonio José dos Santos Neto
Publication year - 2003
Publication title -
vértices
Language(s) - Portuguese
Resource type - Journals
eISSN - 1809-2667
pISSN - 1415-2843
DOI - 10.5935/1809-2667.20030015
Subject(s) - humanities , mathematics , physics , combinatorics , philosophy
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