Lect 23: Shortest Path Problem (post # 2)

(Guest post by John Barker)

We began the class by quickly going over the proof we did the previous lecture regarding the greedy algorithm for the scheduling problem and proving that it outputs the optimal solution.

Atri also quickly showed us how to do the same proof by induction. [To be more precise, I mentioned that the claim that if there is an inversion then there is also a "consecutive" inversion, which we proved last lecture can also be done by induction. --Atri]

The max lateness of  the max lateness of

1. All the jobs before and have the same lateness.
2. All the jobs after and also have the same lateness.
3. The lateness of in the lateness of in .
4. The lateness of in the lateness of in . (The lateness of in the lateness of in .)

We then began to look at the shortest path problem.

Shortest Path Problem

• Input:    A directed graph . For all that exist in and , a start vertex exists in .
• Output: Shortest path for all from
  Def: .
  minimum over all connecting to
  For all , output such that

The graph is directed, all edges have a length greater than , and there is a start vertex in . Note that to have an undirected graph is trivial because any undirected graph can be turned into a directed one, ie. an edge in an undirected graph can become two directed edges connecting each vertex to the other. The algorithm should output the shortest path from to with denoting the minimum path and being the value we are interested in comparing to

Our first guess was to look at a naive algorithm that is not at all efficient but would accomplish what we want. The naive algorithm would have to find all possible paths for all possible combinations, which is . Each path found would require (to verify if the path is the shortest path seen so far for the vertices) so altogether the naive algorithm would take time.

We then looked at algorithms we were already familiar with that might do the job and we decided the BFS would do the trick. Note that this algorithm will only work given that the graph’s edges have equal weight. The layer of the BFS, has vertices that  end up being the distance from the root that we are interested in.

We then studied an algorithm due to Edsger Dijkstra (developed in 1959) who won the Turing Award for his contributions. The Turing Award is given to those who make significant contributions to Computer Science.

In Dijkstra’s algorithm, you start with vertex and maintain a set of ‘explored’ vertices . For , define .

You have  shortest paths in that you maintain and build greedily, at each adding the length of edge to the shortest path .

The algorithm (which can be found in the book)

1. .
2. While there exists a , such that with
   • pick that minimizes
   • add to (and set –Atri).

Atri then showed a quick example of how the Dijkstra’s algorithm works.