# Lab: Shortest paths

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

## Preparation

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.

## Exercises

### Exercise 1: Planning for Dijkstra’s algorithm

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?

### Exercise 2: Implementing Dijkstra’s algorithm

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.

### Exercise 3: Experiments

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!)

## For those with extra time

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

## Some notes on implementing Dijkstra’s algorithm

### Finding “the nearest unknown vertex”

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.

### Paths

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.

### Other data structures

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