- Assigned
- Monday, 6 May 2024
- Summary
- We explore techniques for finding the shortest path in a graph.

If you haven’t done so already, fork and clone the repository at https://github.com/Grinnell-CSC207/graphs and then import it into your IDE.

*Driver: B*

As you may recall, Dijsktra’s algorithm works something like the following:

```
To find the shortest path from SOURCE to SINK,
Indicate that all vertices have infinite distance from SOURCE
Indicate that SOURCE has a distance of 0 from itself
While unmarked(SINK) and there exists an unmarked node with finite distance from SOURCE
Find the nearest unmarked vertex, U
Mark U
For each unmarked neighbor, V, of U
If distanceTo(U) + edgeWeight(U,V) < distanceTo(V)
Note that the best known path to V is the path to U plus the
edge from U to V.
Update the distance to V
Report the path to SINK, if there is one
```

a. How will you represent the path to each vertex?

b. How will you represent the distance (sum of edge weights) from the source to each vertex?

c. How will you “find the nearest unknown vertex”, particularly given that the distance of vertices can change?

d. How will you mark vertices?

*Driver: A*

Implement a method, `shortestPath(int source, int sink)`

, that finds the shortest path from `source`

to `sink`

in the current graph.

If you’re unsure about how to deal with various aspects of the algorithm, you can find some notes at the end of this lab.

*Driver: B*

Write a few experiments or tests to ensure that your implementation does, indeed, find the shortest path. You can likely find some good graphs by doing a Web search for “shortest path example”. (Make sure to cite!)

If you have extra time, go back to the tree traversal lab.

While it is tempting to use Java’s built-in
`PriorityQueue`

for our collection of unmarked neighbors, there are some subtleties involved. As we noted, the priority of a vertex can change as we find new paths. How do we handle that? If we were using a heap and had a link to the node in the heap, we could “heap up” from that location. Of course, that changes the positions of other nodes, which would be problematic.

One strategy is to do without the `PriorityQueue`

, keep a list of unmarked vertices, and do a linear search on that list.

Another strategy is to use the `PriorityQueue`

, but re-insert the vertex with its new priority each time we update the priority. Doing so means that when we remove vertices from the queue, we will need to recheck their priority.

You will likely find it easiest to represent the paths with an array of incoming edges, as we did in the `path`

method in `Graph.java`

.

You will likely find it easiest to represent the distance as an array of integers indexed by the vertex number. Use `Integer.MAX_VALUE`

for “infinity”.

To determine whether a vertex is known or unknown, you can either use the `mark`

method or check whether there is an incoming edge to the vertex (using the array just mentioned).