## Navigating the Codebase for Dijkstra’s Algorithm¶

### 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

### Mazes¶

The `mazes.entities`

package contains basic data structures representing individual components of the maze. The `Wall`

and `Room`

classes should be the only ones you need to interact with directly to complete the assignment.

## Mazes Package

- The
`mazes.gui`

package includes all the GUI code; you shouldn’t need to reference these files, but you’re welcome to take a look if you’re curious. - The
`mazes.logic`

package contains all the main application logic—the code used to generate and solve mazes.`mazes.logic.generators`

contains the generators for grid-based and Voronoi-based mazes.`mazes.logic.carvers`

contains the maze “carvers”—the random removal carver and the Kruskal-based on that you will implement later.`mazes.logic`

also includes a`MazeGraph`

class that serves as the primary graph representation used throughout the application, but the class itself does not contain much code and merely extends a graph from the`graphs`

package instead.

## Solving Mazes¶

### 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 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`

.

### Sample Lazy Reference Implementation¶

The `LazyShortestPathFinder`

class provides examples for working with the other interfaces. However, the code doesn’t actually compute correct shortest paths most of the time, but the syntax for using `Graph`

, `BasicEdge`

, and `ShortestPath`

is correct.

### Dijkstra Implementation¶

Task

Implement `DikstraShortestPathFinder`

using a slightly modified version of Dijkstra’s algorithm.

With all the interfaces out of the way, you can finally start implementing Dijkstra’s algorithm (although it might be helpful to review the lectures and sections on the shortest path tree first).

Some implementation notes:

- 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, to initialize values for new vertices as they are encountered.
- Additionally, since the maze 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.

Once you’re done and all your tests are passing, try re-running the program and click the “Find shortest path” button. If everything went well, the program should now draw a red line connecting the start and the end! (Or display an alert box, if there is no valid path.)

## 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.

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

If you find yourself stuck on a bug for hours, please drop by Office Hours or post on Ed! We are here to help :)

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 where least-cost path has more edges than other paths:

Graph requiring relaxation:

Graph not requiring relaxation:

## Submission¶

Task

Submit to Gradescope and see if you pass all of the tests (info on grader-only tests). Once you are ready, add all of your project partners as Gradescope group members.

Warning

We consider misuses of Gradescope’s group feature to be academic misconduct. This includes submitting another student’s repository without tagging them as a group member, and similarly, adding another person who isn’t actually part of your project team as a Gradescope group member.

If you’re working in a group, the partner who submits must **add the other partner as a group member** on Gradescope. Here’s a video demonstrating that process. You’ll also need to re-add group members whenever you resubmit to the same assignment, even if you already did so on a previous submission.