First of all, what is Depth-First Search? Depth-First Search is a recursive algorithm to “search” through all of the nodes in a graph. How it works is like so: Starting off with a node, we mark it as visited, then for each of its neighbors that is not visited, we call depth first search on them.

Have you ever wondered how Google Maps finds you a shortest path from A to B? It may seem a bit magical at first, but this problem, called the single source shortest paths problem, is very well known! In addition, many efficient algorithms have been developed to solve it. Before we proceed further though, let us first clearly answer the question: What is the single source shortest paths problem? Put simply, the single source shortest paths problem is the problem of finding the shortest paths from a source to all other nodes in a graph with weighted edges. One of…