A Eficiência Polionomial do Simplex para Redes: Aplicação em um problema do caminho mais curto
DOI:
https://doi.org/10.5935/1809-2667.20030015Palavras-chave:
Algoritmo simplex para redes, Complexidade, Árvores de buscaResumo
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.Downloads
Referências
AHUJA, R. K; MAGNANTI, T. L; ORLIN, J. B. - Network Flows, Theory, Algorithms and Applications. Prentice-Hall, Inc, 1993.
BELLMAN R. On a Route Problem. Quarterly Applied Mathematics 16 p 87-90. 1958.
CUNNINGHAM, W. A Network Simplex Method. Math. Programming 11. p.105-116. 1976.
DIJKSTRA, E W. A Note on Two Problems in Connexion with Graphs. Numerishe Matematik, vol. 1. p 269-271. 1959.
FORD, L R. Network Flow Theory. The Rand corporation Report p.923, Santa Monica, CA. 1956.
GOLDFARB, D. AND JIN, Z. An O(nm) Time Network Simplex Algorithm For the Shortest Path Problem. Operations Research, vol.47, N0 3. p 445-448. 1999.
GOLDFARB, D; HAO, J. AND KAI, S.-R. Efficient Shortest Path Simplex Algorithms. Operations Research, vol. 38 No 4, p 624-628. 1990a.
GOLDFARB, D; JIANXIU H; KAI S. R. Anti-Stalling Pivot Rules For The Network Simplex Algorithm. Networks. John Wilev and Sons, Inc. vol.20 p 79-91. 1990b.
LAWLER, E L. Combinatorial optimization: networks and matroids. Holt, Rinehart and Winston, New York. 1956.
MARINHO, C.E.V. Eficiência Polinomial do Método Simplex para Redes: Análise Sobre um Problema do Caminho mais Curto (PCMC). Tese de Mestrado - UENF. Campos dos Goytacazes, RJ- Brasil. 2001.
MOORE, Z F. The Shortest Path Through a Maze. Proc. Internat. Sympos. On Theory of Switching, Part II, p. 285-292. 1957.
ORLIN, B. J. A Polynomial Time Primal Network Simplex Algorithm For Minimum Cost Flows. The Mathematical Programming Society Inc, Published by Elsevier Science B.V-p. 109-127. 1997.
TAHA, H. A. Operations Research: An Introduction. Prentice Hall Inc, 6th Edition. 1997.
Downloads
Edição
Seção
Licença
Os autores do manuscrito submetido à revista Vértices, representados aqui pelo autor correspondente, concordam com os seguintes termos:
Os autores mantêm os direitos autorais e concedem sem ônus financeiro à revista Vértices o direito de primeira publicação.
Simultaneamente o trabalho está licenciado sob a Licença Creative Commons Atribuição 4.0 Internacional (CC BY 4.0), que permite copiar e redistribuir os trabalhos por qualquer meio ou formato, e também para, tendo como base o seu conteúdo, reutilizar, transformar ou criar, com propósitos legais, até comerciais, desde que citada a fonte.
Os autores não receberão nenhuma retribuição material pelo manuscrito e a Essentia Editora irá disponibilizá-lo on-line no modo Open Access, mediante sistema próprio ou de outros bancos de dados.
Os autores têm autorização para assumir contratos adicionais separadamente, para distribuição não exclusiva da versão do trabalho publicada na revista Vértices (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial neste periódico.
Os autores têm permissão e são estimulados a divulgar e distribuir seu trabalho online na versão final (posprint) publicada pela revista Vértices em diferentes fontes de informação (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer tempo posterior à primeira publicação do artigo.
A Essentia Editora poderá efetuar, nos originais, alterações de ordem normativa, ortográfica e gramatical, com o intuito de manter o padrão culto da língua, contando com a anuência final dos autores.
As opiniões emitidas no manuscrito são de exclusiva responsabilidade do(s) autor(es).
Como Citar
1.png)
