# Outline of Class 49: Reachability and Shortest Path Algorithms

Held: Friday, May 1, 1998

• Sorry, I wasn't able to grade the exams for today. They will be graded for Monday.
• Reminder that the cool Math/CS picnic is today!
• Congratulations to Vivek for being elected to president of the International Students Organization.
• Thanks for being nice to my mother.

## Reachability Analysis

• Reachability is perhaps the simplest graph algorithm. Starting at one node in a graph (directed or undirected), determine if you can reach another node in that graph (or how many steps it takes).
• Note that this is, in effect, a variant of the legendary "six degrees of Kevin Bacon" game (see the Oracle of Bacon at Virginia).
• We might begin by a "mathematical" definition of reachability. B is reachable from A if
• B is the same node as A.
• There is an edge from A to B (between A and B).
• There exists a node, C, such that C is reachable from A and B is reachable from A.
• We can simplify this slightly. B is reachable from A if
• B is the same node as A.
• There is an edge from A to C and B is reachable from C.
• (How might you prove these equivalent?)
• Note that we can turn this definition into an algorithm.
```static boolean pathBetween(GraphNode source, GraphNode destination) {
// Base case
if (source.equals(destination)) return true;
// Recursive case: see if there's a path from
// a neighbor to the destination.
for(Iterator neighbors = source.getNeighbors());
neighbors.hasMoreElements(); ) {
GraphNode neighbor = neighbors.nextElement();
if pathBetween(neighbor,destination) return true;
}
// If we reach this point, we've effectively tried every
// possible way to reach the destination.  It must not
// be possible.
return false;
} // reachable
```
• A problem with this algorithm is that there may be an edge back to A, so we may end up revisiting A without ever finding a solution.
• Consider
```   +----+
|    ^
v    |
A -> C -> D -> B
```
• How might our algorithm progress?
```Is there a path from A to B?
Is B equal to A?  No.
Pick some neighbor of A.  C is the only one.
Is there a path from C to B?
Is B equal to C?  No.
Pick some neighbor of C.  Let's pick A.
Is there a path from A to B?
Is B equal to A?  No.
Pick some neighbor of A.  C is the only one.
Is there a path form C to B?
...
```
• How do we fix this problem? By keeping track of which nodes we've visited.
```static boolean pathBetween(GraphNode source, GraphNode destination) {
// Note that we've seen the source.
mark(source);
// Base case: we're already there.
if (source.equals(destination)) return true;
// Recursive case: try all the neighbors.
for(Iterator neighbors = source.getNeighbors());
neighbors.hasMoreElements(); ) {
GraphNode neighbor = (Node) neighbors.nextElement();
if (!marked(neighbor) && pathBetween(neighbor,destination)) return true;
}
// Tried everything.  Give up.
return false;
} // reachable
```
• This gives a "depth-first" search of the tree. As you may have noted from the exam, we could also write this as more generically as:
```/**
* Determine if there is a path from source to destination in the
* "current" graph.  nodes_to_check is used to govern the order
* in which nodes are checked.  If it is a queue, we do a breadth-first
* search.  If it is a stack, we do a depth-first search.
*/
public boolean pathBetween(GraphNode source,
GraphNode destination,
Linear nodes_to_check) {
// Clear the collection of nodes_to_check for safety's sake.
nodes_to_check.clear();
mark(source);
// Keep going until we reach the destination or run out of
// nodes.
while (!nodes_to_check.empty()) {
GraphNode next_node = nodes_to_check.remove();
// Have we found it?
if (next_node.equals(destination) {
return true;
}
// If we haven't found it, note that we should check all
// of its neighbors.
else {
Iterator neighbors = next_node.getNeighbors();
while (neighbors.hasMoreElements()) {
}
} // else
} // while there are nodes left to check
// We've checked all the nodes reachable from the source
// node.  None of them is the destination.  Give up.
return false;
} // pathBetween
```
• We may try this algorithm on a few larger examples.

## Shortest Path

• The shortest path algorithm finds the shortest path from A to B in a graph. The shortest path from A to B is a path from A to B whose cost (determined by some cost function) is less than any other path from A to B.
• The problem generally applies to directed, weighted graph.
• The cost function is often the sum of the weights of the edges on the path, but it might involve other combinations, such as
• the average of the weights
• the product of the weights
• some function of weights and number of edtges
• ...
• Typically, the weights on the graph are nonnegative.
• If the graph includes negative weights and cycles, there may be no shortest path, as there may be a cycle which decreases the cost each time it is taken.
• Depending on the algorithm we develop, there may also be other restrictions on weights, structure, or cost function to ensure that there is a clear shortest path.

### A Brute-Force Solution

• In general, shortest paths don't involve cycles. If we can guarantee that this is the case (e.g., if all weights are positive), then there is a very simple method for finding shortest path.
• List all acyclic paths.
• Compute the cost of each path.
• Pick the smallest such cost.
• This guarantees that we get a correct answer. Why? Because it explicitly matches the definition of shortest path.
• What is the running time of this algortihm?
• It is clearly proportional to the number of paths in the graph times the cost of determing the cost of each path.
• So, how many distinct paths are there in a graph? What does it depend on?
• Note that for graph algorithms, we tend to use n for the number of nodes in the graph and m for the number of edges.

On to Dijkstra's Shortest Path Algorithm
Back to Introduction to Graphs
Outlines: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
Current position in syllabus

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.