小步最短路径算法性能测试及与Dijkstras最短路径算法对比

    基于SNAP库，我们在9个无向图（bio-CE-GN，bio-CE-CX，bio-DM-CX，bio-HS-CX，bio-SC-HT，bio-human-gene1，bio-human-gene2，bio-mouse-gene，bio-WormNet-v3），10个有向图（USairport500，OClinks_w_chars，OClinks_w 和 celegans_n306，Cross_Parker-Consulting_info，Cross_Parker-Consulting_value，Cross_Parker-Manufacturing_aware，Cross_Parker-Manufacturing_info，Freemans_EIES-1_n48，Freemans_EIES-2_n48）上，进行了测试。

    在前12个较大数据集上（节点数量大于等于500），小步最短路径算法均优于，Dijkstras最短路径算法。下面是bio-WormNet-v3数据集上的10个样本截图。

附件是一次采样50个迭代起点的运行结果（各个数据集独立的压缩包总是上传失败，上传的合并的文件），各字段以此是：

    1 确定最短路径的节点数量，

    2 小步最短路径算法访问的边数量/确定最短路径的节点数量，

    3 Dijkstras最短路径算法调用 make_heap的数量/确定最短路径的节点数量，

    4 Dijkstras最短路径算法的运行时间/小步最短路径算法的运行时间，

    5 迭代起点的节点id，

   6 小步最短路径算法访问的边数量，

   7 Dijkstras最短路径算法调用 make_heap的数量，

   8 小步最短路径算法运行占用的时钟周期数，

   9 小步最短路径算法的运行时间（单位s），

  10 Dijkstras最短路径算法运行占用的时钟周期数，

   11 Dijkstras最短路径算法的运行时间（单位s）。

   其中，前4个字短在模型预测中有使用。监测数据表明：

   采用堆实现的Dijkstras最短路径算法的瓶颈在于，当发生更新堆中节点最短路径值时，需要进行make_heap的次数，它占Dijkstras使用时间的75%左右；

   采用堆实现的小步最短路径算法的瓶颈在于，需要跳过邻接边时判断节点是否已经找到最短路径。而这个代价在Dijkstras最短路径算法中，也是存在的。

      下图是单独在bio-WormNet-v3数据集上的测试，需要进行make_heap的次数占Dijkstras使用时间的92.8%。   

     采用线性回归计算器https://stats.blue/Stats_Suite/multiple_linear_regression_calculator.html，使用附件中的前4列数据得到的模型为：

       y = 0.529069 + 0.001171*x1−0.244538*x2+11.44256*x3+0*x1*x1−0.000601*x1*x2+0.002448*x1*x3−28.128116*x3*x3。其中，

          y对应    4 Dijkstras最短路径算法的运行时间/小步最短路径算法的运行时间;

         x1对应    1 确定最短路径的节点数量；

        x2对应    2 小步最短路径算法访问的边数量/确定最短路径的节点数量；

        x3对应    3 Dijkstras最短路径算法调用 make_heap的数量/确定最短路径的节点数量。

     另外，在更大规模数据集datagen-8_2、datagen-8_1、datagen-8_0、datagen-7_9（https://ldbcouncil.org/benchmarks/graphalytics/，https://repository.surfsara.nl/node）等上的测试，其性能提升数百倍。因为内存的限制（16G内存），只能测试最大一亿多边的数据集（134,267,822    M    datagen-8_1-fb.tar.zst）。代码地址 https://github.com/idler66/SmallStepShortestPath。

数据集8_1

（我只测试了datagen-7_5、7_6 、7_7 8_2、8_1、8_0、7_9几个数据集）。