Successive shortest path algorithms for a class of network problems

مرکز و کتابخانه مطالعات اسلامی به زبان های اروپایی

منو

" Successive shortest path algorithms for a class of network problems "
M. S. Al-Ghassab

Document Type	:	Latin Dissertation
Language of Document	:	English
Record Number	:	1112867
Doc. No	:	TLpq230908888
Main Entry	:	M. S. Al-Ghassab
Title & Author	:	Successive shortest path algorithms for a class of network problems\ M. S. Al-Ghassab
College	:	King Fahd University of Petroleum and Minerals (Saudi Arabia)
Date	:	1994
student score	:	1994
Degree	:	M.S.
Page No	:	192
Abstract	:	The focus of this thesis is on a class of network problems consisting of the assignment, the semi-assignment and the transportation problems. The major objective of the thesis is to extend the successive shortest path (SSP) algorithm proposed for the assignment problem to solve the semi-assignment and the transportation problems. Then implement the SSP algorithm for these two problems and test their efficiency in comparison with available algorithms. The first part of this thesis is devoted to identifying which shortest path algorithm best fits the SSP algorithm proposed for the assignment problem. It has been confirmed that an implementation of a label-setting algorithm by Dijkstra is the best shortest path algorithm which best fits the SSP approach. The SSP algorithm for the assignment problem was found to be the most efficient in terms of computational time for solving sparse problems. The SSP algorithm for the semi-assignment problem has a computational bound usdO(n\sp3)usd and outperformed CAPNET (an implementation of a specialized simplex algorithm) and TRANS which is an implementation of Out-of-Kilter algorithm. The generalized SSP algorithm for the transportation problem is implemented and found to be 1.3 times faster than CAPNET for low cost range problems.
Subject	:	Applied sciences
	:	Systems design