期刊文献+

最大流最小费用的一种简洁算法

An Algrothm of Maximum Flow with Least-Cost
下载PDF
导出
摘要 一、引言 对于一个输运网络,已知发点的数目、位置和发量,收点的数目、位置和需求量,及网络中各边的容量,求使总运费最省的调度方案,这是线性规划解决的典型问题,Busacker与Gowen也就该问题将可行流与迭代、反圈法结合起来求解。 本文拟将图论中的求最短路径及求最大流的两种算法结合起来,提出该问题的一种简洁实用的解法。 本文的算法较线性规划解法与Busacker和Gowen的算法而言的优点在于:物理意义明确;可与图形显示系统结合起来进行流过程的动态模拟,形式更加简洁有效。 The problem is for a traffic network, given the numbers, positions and the amount of supply or re-quirment of original and terminal points, and given the capacity limit of each network line, how to find the optimal traffic plan with least traffic cost. The paper links two algrothms of shortest route and maximum flow to solve the problem. The algrothm consists of three continuous procedures: 1. Finding the shortest route between original and terminal points with the Dijkstra algrothm; 2. Labelling along the shortest route; and 3. Increasing the folw along the labelled shortest route. The three steps are to be repeated until the terminal point can not be labelled. The graphic algrothm can be related with dynamic chisplay system to simulate and analyse the transport flow and transport scheme.
作者 王劲峰
出处 《甘肃科学(甘肃科学院学报)》 1990年第4期19-21,共3页
关键词 输运网络 Dijkstra法 标号法 Traffic network, dijkstra algrothm, labelling procedure.
  • 相关文献

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部