最短路径算法 数据读写 优化方法

        Dijstras最短路径算法用松弛操作，通过更新节点的路径值来计算，图中节点的最短路径。该方法的系统开销主要在于，松弛操作对路径值的重复读写，尤其是记录单个节点的路径值需要多个比特的数据，对缓存系统冲击大，读写有效性大大降低。

        小步最短路径算法在逐步增加路径长度的过程中，依次确定节点的最短路径，不存在无效的路径值更新。该方法的系统开销主要在于，对已确定最短路径节点的邻接边的间断处理及其对节点是否确定最短路径标记的读写，尤其是重复读标记对缓存系统读写性能带来的挑战。

       因此，无论是使用松弛操作的Dijstras最短路径算法，还是小步最短路径算法，都存在对计算机缓存系统读写冲击大，进而导致算法执行效率低的问题。该数据读写优化方法，尤其是对小步最短路径算法的优化是尤为明显。

       具体步骤为：       

1. 从有向图中选择预设数量的未划分等价类的节点；

   将选择的节点作为根节点，根据所述根节点及上限节点基数，从所述根节点最近的未划分等价类的节点中确定根节点的最短路径树；

   根据根节点的最短路径树中的最短路径信息及节点信息，从所有根节点的最短路径树中确定一个最优树，将所述最优树包含的节点划分为一等价类；

   重复上述步骤，直至所述有向图中所有节点均已划分等价类；

2. 编码所述等价类及等价类中的节点，得到各等价类的二元组；
3. 根据所述等价类的二元组，将所述等价类中节点的相关数据在联系的内存中存储。

        对于Dijstras最短路径算法，当节点确定最短路径后，可通过查询1比特的标记位，避免路径值的读取；当节点未确定最短路径值时，引入了额外的查询1比特的标记位的代价；在多个数据集上的测试显示，性能提升大约20%左右。

       因为小步最短路径算法是一次性确定的，节点的最短路径值只需依次记录在一个线性表中，完全不需要读操作，即只需要对一个bit的标记位的一次写和多次读操作，有较大的性能提升，使用该方法后，小步最短路径算法的主要资源消耗从节点是否获取最短路径的标记位的读写（这种邻接边属性的间断性读取的方式的性能，略低于，Dijstra最短路径算法的邻接边属性读取方式的性能），转变为节点邻接边的访问。 通过该方法，我们可通过高速缓存的预加载，来进一步提高小步最短路算法的效率。

      小步最短路径算法的合理性和优越性来自于矛盾的集中，即避免Dijstra最短路径算法的不必要的数值计算和比较操作，使其集中到节点是否确定最短路径的1比特的标志位的读取操作。只有矛盾集中起来，才能得到有效的解决。Dijstra最短路径算法把问题分散在逻辑判断、数值计算、高速缓存读写的效率等等方面，针对这种情况我们是很难给出大幅的提升和改进的。