网络优化算法的实现与比较  

Implementation and comparison of network optimization algorithms

作　　者：白洪涛[1] 孙吉贵[1] 焦洋[1] 徐长青[1] 

机构地区：[1]吉林大学计算机科学与技术学院,吉林长春130012

出　　处：《吉林大学学报（信息科学版）》2002年第2期59-69,共11页Journal of Jilin University（Information Science Edition）

基　　金：国家自然科学基金资助项目 (60 0 73 0 3 9) ;教育部骨干教师基金 (2 0 0 0 5 40 ) ;吉林省自然科学基金资助项目

摘　　要：以实际“物流决策支持系统”项目为背景 ,讨论了网络的邻接矩阵、关联矩阵、邻接表、弧表、星型表示法等计算机存储表示在处理实际问题时的优缺点 ,选用邻接矩阵、邻接表表示法设计实现了最短路算法和最大流算法 ,通过分析、测试 Ford-Fulkerson算法、最大容量增广路算法、Dinic算法、最高标号预流推进算法等 。The presentation of computer network storage such as adjacency matrix, incidence matrix, adjacency lists, arc list and star is discussed based on the 'Materials Circulation Decision Support System' project.The shortest path algorithms and maximum flow algorithms are designed and implemented using adjacency matrix and adjacency lists. Those algorithms such as Ford Fulkerson algorithm, max capacity augmenting path algorithm, dinic algorithm, highest label preflow push algorithm etc are analyzed and tested. The adaptability and run time efficiency of different implementation of each algorithm is also presented.

关 键 词：最短路径 最优化理论 最大流算法 网络优化 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]