Graph Theory Questions

1) Linear-time shortest path (3 pts)

In a weighted directed acyclic graph, how could you find the shortest
path between two given vertices in linear time (that is, O(V+E))?

2) Graph Algorithms (3 pts)

Each of these problems can be solved easily by a graph
algorithm. Indicate, for each problem, which of the following
algorithms you would use: Dijkstra's Algorithm, Prim's Algorithm,
Topological Sorting, Breadth-first Search, Depth-first Search. Give a
one-sentence explanation for each of your choices.

 2a) (1 pt) A student needs to take a certain number of courses to
graduate, and these courses have prerequisites that must be
followed. Assume that ALL courses are offered every semester and that
the student can take ONE course each semester. How can she find an
appropriate sequence to take?

 2b) (1 pt) A word can be changed to another word of the same length
by a series of single-character substitutions (with no additions or
deletions). Given two words of the same length, how could we find out
if we could change one into the other so that all of the intermediate
strings are valid words? For example, bleed converts to blood by the
sequence bleed, blend, blond, blood.

 2c) (1 pt) Suppose you are working at a cable TV company. How could
you design an optimal cable wire plan such that all the customers are
connected and the total length of the cable is as small as possible?

3) BFS versus DFS (4 points)

Suppose we use BFS and DFS to find a path from some starting vertex to
an ending vertex in a graph.

 3a) (2 points) Will BFS and DFS always return the same path between a
pair of vertices in a tree? Give a explanation about why or why not.

 3b) (2 points) In general, will DFS and BFS always return the same
path between two vertices in any graph? Give a brief explanation about
why or why not.