<I style="mso-bidi-font-style: normal">Application of the fastest path algorithm to finding maximum concurent multicommodity linear flow with minimal cost on extended traffic network<?xml:namespace prefix = "o" ns = "urn:schemas-microsoft-com:office:office" /><o:p></o:p></I>

Abstract

Extended graph and network is a powerful mathematical tool applied in many fields such as transportation, communication, informatics, economy, … [7]. The main result of this paper is to design a Maximum Concurent Multicommodity Flow with Minimal Cost algorithm on extended traffic networks using the algorithm to find shortest paths on extended networks [6]. On the basis of the dual linear programming problem studied in [7], the author designs the algorithm to reduce the ratio of objective values of the dual and the primal problems down to 1. Then, it follows the concurent maximal flow with minimal cost of the origin problem. This algorithm is an approximate algorithm with a (1+w)-approximation ratio, where w is an arbitrary positive. The paper analyses, proves obtained results, as well as evaluates the running time. The algorithm is coded in the programming language Java with extended network database in the database management system MySQL and gives exact result.<?xml:namespace prefix = \"o\" ns = \"urn:schemas-microsoft-com:office:office\" />