neo4j计算最短路径

作者: 联合国抬杠队秘书长
来源: 51数据库
2020-09-30

主要是有三种、、

第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、

第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、

第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、

　　以起点为首节点开始分支，分支的个数就是当前节点有几个位置可以走，节点内容为当前所在迷宫位置就这样不停的分支，每生成一个节点就判断是否为终点位置，是则得出结果，输出路径。因为生成的树的层数对应的正是已走的步数，所以第一个结果必是最短的另外在数据结构上可以多设计一个数组记录已经走过的位置，当生成的节点位置已经被走过，则可删除该节点，这样可以减少搜索次数。这是类似的广度搜索，如果数据量不多，用递归会更直观，简单。

推荐阅读