【摘要】 针对无回路网络的特殊性,利用广探法的思想,提出了无回路网络最短路的有效算法,并在此基础之上提出了最小费用流的有效算法。其算法的复杂性分别为o(m)和o(mvo),相比拓扑排序法和最小费用路算法,本文提出的算法更为简练、易懂且复杂性低。更多还原

【Abstract】 According to the Special nature of the DAG,A high-efficient algorithm to seek the shortest path in DAG is presented by the idea of breadth first search,on this basis,we Propose an algorithm for the minimum cost flow in DAG.The Complexity of the two Algorithms are respectively in time o(m) and o(mvo).Correlative analysis and instances indicate that this algorithm is superior to other current algorithms in respect of computing complexity,operation,etc.更多还原