面向云计算框架的最大流算法实现研究

Study on Implementation of Maximum Flow Path Algorithm for Cloud Computing

网络最大流路径搜索是图论中的一种重要方法,在交通路径规划、通信路由寻址等领域具有广泛的应用.然而,随着实际问题规模的增大,抽象出的网络模型越来越复杂,最大流路径的搜索过程也越来越耗时,甚至丧失其时效性.为提高计算速度,对最大流搜索算法进行了改进,并采用MapReduce分布式编程模式实现了该算法.基于开源云计算框架的实验表明,改进的算法及其在云计算平台上的实现,对于大规模网络有着较好的搜索效果和计算性能.

Searching for the maximum augmented flow path is a crucial problem in graph theory. It is ap- plied comprehensively in most fields, such as the computation of travel path in transportation planning and the routing solution of network data flow in communication systems. However, the abstract network model is becoming more complex as the scale of the studied system increases. It causes the path searching process much more time consuming, and the obtained results even lose their timeliness. In order to increase the computing speed, this paper improves the maximum flow path searching algorithm, and implements the algorithm by the MapReduce distributed programming model. The experiment based on Hadoop,an open source cloud computing platform, indicates that the improved algorithm and its implementation in the cloud computing platform have better searching efficiency and computing performance for large scale networks.