• We survey and summarize MCNF problems and algorithms that have appeared in the last two decades.
• We survey and summarize shortest path algorithms that have appeared in the last five decades.
• We observe the connection between a new shortest path algorithm and the well-known Dijkstra's algorithm.
• We propose three new multiple pairs shortest paths algorithms, discuss their theoretical properties, and analyze their computational performance.
• We give two new MCNF algorithms, and compare their computational performance with two standard MCNF algorithms.

       This thesis has six chapters. Chapter 1 discusses MCNF applications and their formulations. Chapter 2 surveys MCNF solution techniques from the literature. Since our approaches require us to solve many multiple pairs shortest paths (MPSP) problems, we will propose new efficient MPSP algorithms. Chapter 3 first reviews the shortest path solution techniques that have appeared in the last five decades, and then introduces a new shortest path method which uses the nonnegative least squares (NNLS) technique in the primal-dual (PD) algorithmic framework, and discusses its relation to the well-known Dijkstra's algorithm. Chapter 4 discusses the theoretical details of our new MPSP algorithms. Chapter 5 presents the computational performance of our new MPSP algorithms. Finally, Chapter 6 illustrates our primal-dual MCNF algorithms, analyzes their computational performance, and suggests new techniques to improve the algorithms. Chapter 7 concludes this thesis and suggests future research.