Technical Perspective: Shortening the Path to Designing Efficient Graph Algorithms

Graph theory is an integral component of algorithm design that underlies sparse matrices, relational databases, and networks. Improving the performance of graph algorithms has direct implications to applications ranging from operations research to computational biology. As a result, the design of faster graph algorithms has received extensive attention, leading to tools with wide reaching implications. One of the most well studied problems in graph algorithms is the shortest path problem. Given weights on edges, compute the shortest path with minimum total weight from vertex s to vertex t.