Graph: Find the Shortest Path

Tasks

Read about the Shortest Path Problem in graph traversal. On that page you’ll find a list of six algorithms for solving the problem. Your task is to implement two of these as methods on your weighted graph.

You must implement Dijkstra’s algorithm, since this is one that is most commonly referenced in interviews. After that, the choice of the second algorithm is up to you.

Write tests that demonstrate that your algorithms correctly solve the problem under a variety of circumstances.

Do your work on a new branch in your data-structures repository. If you have not yet merged your work on weighted edges, you’ll need to branch off of that branch in order to get that version of your graph as a starting point.

Update your README with a description of the algorithms you implement. Include a paragraph describing the factors that might lead you to choose one or the other.

Submitting Your Work

When you are finished with your work and all your tests are passing, create a new pull request from your branch to master. Submit the URL from that pull request. When you’re done with that, you can merge the branch back, but do not delete the working branch until your assignment has been graded.