基于分流算法的最短路径求解算法

Shortest Path Algorithm Based on Diffluence Algorithm

在图论中,一般求最短路径都是通过比较各种可能的路径后而得到的,基本上都是按树的回溯方式求得,算法耗时长。分流算法将路径长度比较转化为等速同时发出的水流的速度比较,用Agent实现水流,让从开始结点出发生成的各水流同时流动,经过最短路径的水流将最先到达最终结点,结果用最短的时间获得最短路径。理论和实践都表明该算法是求最短路径的有效方法。

In graph theory,to getting shortest path must compare all possible path,basically use backtracking,the Algo-rithm needs longer time.The Diffluence Algorithm translates the compare of path length into the compare of speed of streams issuing at one time ,make stream into Agent ,let every stream issuing from start node flow at one time ,the stream through shortest path arrive first final node,as a result gain shortest path with shortest time.Theory and practice indicate that this algorithm is availability method obtaining shortest path.