INFOR Information Systems and Operational Research · 1978 · 19 citations · 4 references
ComputingComputer ScienceMathematicsAlgorithmsOptimizationTheory Of ComputationAlgorithm AnalysisComputational ComplexityGraph AlgorithmsNetwork OptimizationShortest Path AlgorithmsComputational EfficiencyComputational Efficiency AnalysisIncremental Shortest Path AlgorithmsShortest Path ProblemsShortest Paths
Murchland(5) published an algorithm for recomputing all shortest paths after a change in the length of only one arc in a network. We study that algorithm both from a theoretical and a computational point of view. We suggest a slight modification of the algorithm to improve computational efficiency. Murchland deals with the oriented case (dij≠dji da, where dij= length of arc from i to j). We also study the non-oriented case (dij=dji).
4
Robert W. Floyd · Communications of the ACM · 1962 · 4K citations · Full text
An Appraisal of Some Shortest-Path Algorithms
Stuart E. Dreyfus · Operations Research · 1969 · 997 citations