Tabatabai, Bijan Oni (1987) An investigation of shortest paths algorithms. Doctoral thesis, Durham University.
In this work, we classify the shortest path problems, review all source algorithms and analyse the different implementations of single source algorithms using various list structures and labelling techniques. Furthermore, we study the Sensitivity Analysis of one-to-all problems and present an algorithm, Senet, for their Post Optimality Analysis. Senet determines all the critical values for the weight of an arc (which could be optimal, non-optimal or non-existant) at which the optimal solution changes. Senet also provides the updated optimal solution for every range formed by two successive critical values.
|Item Type:||Thesis (Doctoral)|
|Award:||Doctor of Philosophy|
|Copyright:||Copyright of this thesis is held by the author|
|Deposited On:||08 Feb 2013 13:44|