Comments on Programming Assignment 2 (Dijkstra's Algorithm)

equals vs ==: the difference here is between "equivalent" and "same". For objects, == compares addresses so a == b is true only if a and b are at the same place in memory i.e. they refer to the same object. For some types there is also a notion of equivalence — imagine dealing the Queen of Hearts from two different decks of cards. These are not the same card as you have two separate cards lying side-by-side on the table, but they are equivalent because they are interchangeable — you don't care which of the two cards is in your hand because it only matters that you have a Queen of Hearts. equals allows for a definition of equivalence in situations like this. Which to use? Use == when object identity is important (it matters which card even if both are the Queen of Hearts) and equals when it isn't (what matters is the Queen of Hearts vs some other suit and value). Vertex and Edge should be compared with == — object identity matters.

Since there's an init method to initialize the algorithm for starting at a particular vertex, it's nicer if all of the initialization is done there — including creating the data structures. Doing some of the initialization in the constructor can lead to bugs if init is used repeatedly on the same Dijkstra object to start with different vertices.

compare should return -1 when the first parameter should come before the second and 1 in the opposite case. Be careful not to get the comparison backwards unless you mean to order bigger things first.

The typical implementation stores the previous vertex in order to reconstruct the actual path that is the shortest path, but the handout said to instead store the previous edge. This makes getPathEdges more efficient (no need to search incident edges to figure out the edge that connects to the previous vertex) without making getPathVertices less efficient.

contains is O(n) for Java's PriorityQueue, while add and remove (of the first thing) are O(log n). If you are tempted to use contains to decide whether or not to add or remove, consider whether or not you really need to. (Do you already know whether or not the element is there? What are the consequences of adding a duplicate or removing something that isn't there?) remove(Object) is O(n) so using contains in conjunction with it doesn't have big-Oh implications, but it is still worth consider whether or not you need contains.