Finding single source shortest path is a very ubiquitous problem. But with the increasing size of large datasets in important application like social network data-mining, network topology determination-efficient parallelization of these techniques is needed to match the need of really large graphs. We present a new Inter node-bellman cum Intra node Dijkstra technique implemented in MPI to solve SSSP problem. We have used a triangle based edge pruning for idle processes, and two different techniques for termination detection. Within each node the algorithm works as Dijkstra and for outer communication it behaves as inter node bellman ford. First termination detection technique is based on the token ring and counter. Second is a heuristic based technique, in which the timeout is calculated from the number of inter-edges and number of partitions. In this project asynchronous mode of message passing is used.

翻译：寻找单一源的最短路径是一个非常普遍的问题。 但是,随着社会网络数据挖掘等重要应用中大型数据集规模的扩大, 需要将这些技术的网络地形测定和高效平行化, 才能满足真正大图表的需求。 我们展示了在 MPI 中实施的新 Inter node- bellman 和 Intra node Dijkstra 技术来解决 SSSP 问题。 我们使用了基于三角边边线的闲置程序, 以及两种不同的终止探测技术。 在每一个节点中, 算法作为 Dijkstra 和外部通讯工作, 其行为方式是作为 interde bellman 。 第一次终止探测技术以符号环和反向为基础。 第二种基于超光学的技术, 其计算出间隔和分区的超时数。 在此项目中, 使用了信息传递的无节奏模式 。