DijkstraShortestPathFinder

Task

Implement DijkstraShortestPathFinder

Note

In order to make DijkstraShortestPathFinder work with the rest of the program, we have introduced some slight modifications to how it works internally. However, the main logic of Dijkstra’s still follows. Below, you’ll find a brief overview of each of the interfaces that DjikstraShortestPathFinder uses.

Implement a shortest path finder using a modified version of Dijkstra’s Algorithm. Here are a few things to keep in mind as you work through this implementation:

  • You can use the Double.POSITIVE_INFINITY constant to represent infinity.
  • 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 operation to match — initialize values for new vertices as they are encountered.
    • 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.
  • Since Dijkstra’s algorithm relies heavily on a priority queue, we’ve provided an alternate priority queue implementation in the skeleton code.

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.

Graphs Package
  • graphs.Graph: a basic directed graph, with generic type parameters for vertex and edge types.
  • graphs.BaseEdge: the base edge class; always directed and weighted.
    • graphs.Edge: the primary implementation of BaseEdge.
    • graphs.EdgeWithData: a BaseEdge that additionally contains some extra, generic data and is used by MazeGraph.
  • graphs.shortestpaths: contains algorithms for finding shortest paths

Shortest-Path Finder

Note

The interface includes the same generic definitions as MinimumSpanningTreeFinder, but once again, you should be able to safely ignore them—the important takeaway is that G is a Graph, V can be any object, and E is a BaseEdge.

Signature Description
ShortestPath<V, E> findShortestPath(
G graph, V start, V end)		 Computes a shortest path from start to end in a given graph, and returns a ShortestPath object.

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

Signature Description
Map<V, E> constructShortestPathsTree(
G graph, V start, V end)		 Returns a (partial) shortest paths tree (a map from vertex to preceding edge) containing the shortest path from start to end in given graph.
ShortestPath<V, E> extractShortestPath(
Map<V, E> spt, V start, V end)		 Extracts the shortest path from start to end from the given shortest paths tree.

The ShortestPath object returned is essentially a container for edges.

Graph

Signature Description
Collection<E> outgoingEdgesFrom(V vertex) Returns an unmodifiable collection of the outgoing edges from the given vertex.

Note

The method returns a Collection; this means that it’s up to the implementation to decide exactly what Collection implementation to use (usually a List or Set).

Note

The returned Collection is unmodifiable, so any attempts to modify it directly will throw an UnsupportedOperationException.

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.

Graphs used in tests:

Start and end vertices have bold outlines.

Graph with multiple paths between start and end:

Graph with multiple paths between start and end

Graph where least-cost path has more edges than other paths:

Graph where least-cost path has more edges than other paths

Graph requiring relaxation:

Graph requiring relaxation

Graph not requiring relaxation:

Graph not requiring relaxation