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.20030015Keywords:
Algoritmo simplex para redes, Complexidade, Árvores de buscaAbstract
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
References
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
Issue
Section
License
The authors of the manuscript submitted to Vértices, hereby represented by the corresponding author, agree to the following terms:
The authors retain the copyright and grant Vértices the right of first publication.
At the same time the work is licensed under the Creative Commons Attribution 4.0 International License, allowing third parties to copy and redistribute the material in any medium or format and to remix, transform, and build upon its content for any legal purpose, even commercially, provided the original work is properly cited.
Authors will not receive any material reward for the manuscript and Essentia Editora will make it available online in Open Access mode, through its own system or other databases.
Authors are authorized to enter into additional contracts separately for non-exclusive distribution of the version of the work published in Vértices (eg, publish in institutional repository or as book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are permitted and encouraged to disseminate and distribute the post-print (ie final draft post-refereeing) or publisher's version/PDF at online information sources (eg, in institutional repositories or on their personal page) at any time after the first publication of the article by Vértices.
Essentia Editora may make normative, orthographic and grammatical changes in the originals in order to maintain the standard language, with the final consent of the authors.
The content and opinions expressed in the manuscript are the sole responsibility of the author (s).
How to Cite
1.png)
