Shortest Path Finder

Our first seam carving implementation uses a graph, and turns out finding a seam is a shortest path problem: we want to select a path of pixels with the lowest energy, among many other possible paths. This sounds exactly like Dijkstra’s algorithm!

DijkstraShortestPathFinder¶

Implement a shortest path finder using Dijkstra’s Algorithm.

In order to make DijkstraShortestPathFinder work with the rest of the program, we have introduced some slight modifications to how it works internally. Notably, we will implement a more efficient version of Dijkstra’s algorithm, where you might not necessarily know the number of vertices in the graph beforehand to be able to initialize every vertex to infinity and will need to insert the vertices into the distTo map as you encounter them. However, the main logic of Dijkstra’s still follows.

For review, here is a video that describes Dijkstra’s algorithm (accompanying slides):

Below, you’ll find a brief overview of each of the interfaces that DjikstraShortestPathFinder uses. Here are some specific implementation notes that we recommend you keep in mind as well:

• Recall that Dijkstra’s algorithm requires that we start by initializing the distances of all possible vertices to infinity. This isn’t actually possible with our graph interface.
  • Instead of initializing values for all vertices at the beginning of the algorithm, we’ll initialize values for only the starting vertex.
  • This necessitates that we also change our relaxation (neighbor processing) operation to match—initialize values for new vertices as they are encountered.
  • You can use the Double.POSITIVE_INFINITY constant to represent the prior distance to a vertex you have never seen before.
  • Additionally, since the application has a particular destination in mind, our algorithm does not need to compute the full SPT; we can stop as soon as we have found the shortest path from the starting vertex to the destination. As soon as we remove the destination vertex from the queue, the nature of BFS-like algorithms means we have guaranteed to have already found the best path to it, and we can stop the algorithm.
• Since Dijkstra’s algorithm relies heavily on a priority queue, we’ve provided an alternate but slower priority queue implementation, NaiveMinPQ, that you can highly optionally choose to use. Either way, the autograder will swap out your priority queue implementation with ours, so a buggy implementation from the previous assignment should not affect your grade (but may make your testing locally more difficult).
• Remember to use Objects.equals() instead of == to compare objects for equality.

Graphs¶

The graphs package is a generic library of graph data structures and algorithms. Here are a few classes that are related to Dijkstra’s algorithm.

Shortest-Path Finder¶

In the Dijkstra-based implementation that you will be implementing, the method above is broken into two sub-methods:

The ShortestPath object returned is essentially a container for edges. It may be helpful to look at the LazyShortestPathFinder class for examples of how these objects are initialized.

Graph¶

Testing¶

If you find yourself passing our unit tests but failing stress tests on Gradescope, your best course of action will be to carefully review your code until you figure out where your code deviates from Dijkstra’s algorithm.

Some of our stress tests will also check your code’s runtime:

• One test will time your code on random graphs with many vertices and edges (so the shortest paths end up being only several edges in length).
• Another test will check the runtime with very long paths.

If you fail these tests, refer to the pseudocode in the Dijkstra lectures and check to see if you’re following it correctly.

Finally, for your convenience, here are some diagrams of graphs from provided tests.