一种分布式计算有向图围长的方法

摘要

本发明公开了一种分布式计算有向图围长的方法，属于并行与分布式计算技术领域。本发明方法首先将有向图G中所有权值为负的边转化为非负；之后图G中每一个点执行有距离限制参数t的Bounded BFS算法；再根据Bounded BFS算法的结束条件，更新有向图围长g的下界α或上界β；之后根据β、α和Bounded BFS的结束条件，删除图G中权值之和大于α或β的路径；最后通过α和β更新距离限制参数t，重复执行步骤S2‑S5直到β‑α小于等于1，得到图G的围长g＝β。本发明方法旨在设计一个线性时间的分布式计算有向图围长的方法，此方法的时间复杂度为O(nlognlogg)，可在有权图下避免消息拥塞，有效的降低了算法的时间复杂度，保证了在大规模有向图中可以快速的分布式计算图的围长。