Recitation 9

Recitation notes for the week of October 30, 2017.

Dijkstra's Algorithm

Finds the shortest path to all nodes from a starting node, where the edges are weighted.

Walk through a run of Dijkstra's algorithm on the graph below.

If we only care about the distances

The no need to maintain the "Dijkstra tree."

Also if there is a specific end node $t$, then can also stop Dijkstra's algorithm once you have reached $t$.

Runtime Analysis

Note to TA

Walk through the runtime analysis for the case when priority queue is used to find the vertex $w$ that minimizes $d'(w)$. In particular, show the claim (4.15) in the textbook: i.e. one needs at most $n$ ExtractMin and at most $m$ ChangeKey operations.

Necessity of all non-negative edges

Dijkstra's algorithm does not work even if the graph has a single negative edge.

Exercise 1

Walkthrough the run of Dijkstra's algorithm on the following input:

Exchange Argument for Minimizing Max Lateness

Main Idea

If we have a schedule with no idle time and with an inversion, then we can rid of an inversion in such a way that will not increase the max lateness of the schedule.

Recall

In the lecture, we showed that schedules with no inversions and no idle time have the same max lateness.

Given the schedule below where the deadline of $j$ comes before the deadline of $i$ (the top schedule has an inversion):

Let us consider what happens when we go from top schedule to the bottom schedule. Obviously $j$ will finish earlier so it will not increase the max lateness, but what about $i$? Now $i$ is super late.

However, note that $i$’s lateness is $f(j) - d(i)$ where $f(j)$ is the finish time of $j$ in the top schedule. Now note that \[f(j) - d(i) < f(j) - d(j),\] so the swap does not increase maximum lateness.

An Example

Here is an explicit example showing the above proof argument: \[d(a) = 2~~~~ t(a) = 1\] \[d(b) = 5~~~~ t(b) = 6\] \[d(c) = 8~~~~ t(c) = 3\]

Now consider this schedule with inversions: \[__a__|____c____|______b_______\] And another schedule without inversions: \[__a__|______b_______|____c____\]

The first schedule has max lateness of $5$ while the second schedule has max lateness of $2$.

NOTE

Examples do not suffice as proofs. But they are good for understanding purposes.