货运调度系统中的一个最短距离算法

本文结合具体的公路交通图,采用图的节点压缩法和分块技术,实现了货运调度系统中一个求交通图上任意两点间的最短距离的优化算法。

Shortest Path Algorithm for a Goods Transport Dispatching System by Truck

How to find the shortest path between two arbitrarily given points on a highway traffic map is the key problem in a goods transport dispatching system by truck. The node-compressing and graph partitioning techniques are pro-posed and described.On a traffic map all the lines are connected and there exist no isolated nodes (place names). The nodes are classified by the authors into cross and noncross ones. The cross code is defined as one connected to other nodes with many paths and the noncross one as connected to other nodes with only one or two paths. Now, if the path between any arbitrary noncross node and the adjacent cross-node is given, then finding the shortest possible path between two arbitrary nodes on the traffic map would be reduced to finding the shortest path between two nodes on the graph consisting of cross-nodes. Therefore, the original traffic map is simplified to a graph with only cross-nodes and the number of the nodes is decreased at least by half. The amount of computing is greatlv reduced and the operating efficiency of the system improved. Moreover, less storage space is needed.A data file has been worked out and the shortest path algor ithmsfor three different cases, i.e., between two nodes (including cross-nodes and noncross-nodes) in the same block; between the nodes in two adjacent blocks; and between the nodes in the nonadjacent blocks, are given.