Graph Algorithm - Efficient Shortest Path Estimation

Graph systems are getting more and more complex with the boom of social networks and advancements in data mining. Many problems arise as the graphs become massive. Many traditional algorithms for graphs are becoming too time consuming. Therefore, our goal is to design more efficient algorithms for large graphs.

In this project, we proposed a shortest path algorithm that uses MultiDimensional Scaling(MDS) technique to speed up the traversal time. MDS converts graphs into two dimensional maps, and with the assist of MDS, we use greedy routing to find the shortest path. Our greedy algorithm traverses to the closest neighboring node to destination, and repeat the process until the destination is reached. However, since MDS is only an approximation of coordinates, many obstacles arise, such greedy algorithm often comes up with far longer paths than the real shortest path. By creating a statistical model of  200 pairs of samples from the graph, we find that the ratio between real shortest path and direct distance path is no larger than 1.5, therefore by setting such parameter on our algorithm, it drastically increases the accuracy and efficiency. However, there are currently a 10% failure rate at which no paths are returned. Our algorithm is 171.3 times faster than dijsktra’s algorithm on a 1981 nodes graph, while the distances is, on average, 1.54 times longer than dijsktra’s path.