  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.
