Algoritmos para caminhos mínimos

Em Algoritmos para Caminhos Mínimos, Shigueo Isotani descreve algoritmos para o problema do caminho mínimo. Entre os algoritmos considerados está o algoritmo linear de Thorup (M. Thorup, Undirect Single Source Shortest Paths with Positive Integer Weights in Linear Time, Journal of ACM, vol. 46, 362-394). Uma análise experimental da eficiência de tempo e espaço de implementações dos algoritmos é apresentada. As implementações foram feitas no sistema de programação literária CWEB e utilizam a plataforma para algoritmos combinatórios SGB.