Approximate overview
Other good things
Do we need numerous citations?
No. But if you refer to sources (e.g., look at them), please cite.
You can use the movie and your intuition.
Do we have to do general consideration of bias, or can we consinder particular algorithms (or those things they call “algorithms” in the movie).
Either.
You may recall that our analysis was, approximately,
O(n*cost-to-find-nearest-remaining-node + m)
A naive mechanism for finding the nearest remaining node is O(n).
A heap brings it down to O(logn).
So Dijkstra’s algorithm is O(nlogn + m). That’s much better for sparse graphs. If our graph is fairly populated, it’s probably O(n^2).
Sam does not know a formal definition of sparse. But if nlogn « m, this analysis is helpful and this implementation is much faster. We might say O(nlogn) edges is “sparse”, Theta(n^2) edges is “populated”, and everything in between is “something else”.
However, using a heap complicates the implementation significantly, because we need to “re-heap” a value when its distance changes.
Why do we care about shortest path? (TPS)
“It’s good for optimizing things”
Note: Other kinds of graph optimizations, such as, “the path with the largest smallest edge”
“More general optimizations”
“Other reasons”
TPS
You, paraphrased
I’m not sure why so many people insist on proofs of correctness. They are usually annoyingly detailed, but also relatively straightforward. More importantly, they reveal little important about the algorithm.
Rebelsky, paraphrased
Nonetheless, there are many “algorithms” that look correct at first glance. And second glance. Proofs help us ensure that they are correct (or help us find counter-examples).
Unfortunately, many of us are as likely to make mistakes in our proofs as we are in our algorithms.
Practice is good.
The argument
By induction.
Midway through, we have two sets: V (all vertices) and X (verticies we’ve marked). Dijstra’s algorithm chooses the element, e, in V-X that is “closest” to start node, given the knowledge so far.
Why is this acceptable? If we go through some other node in V-X, the path must be longer.
Quick survey: Who has seen/done this before?
Suppose, instead of the shortest path from S to T or from S to any node, we want all of the shortest paths. That is, for all pairs S,T in the graph, we want the shortest path from S to T. (We’re building a matrix, this must be at least n^2 work.)
For each node, run Dijkstra.
Running time? O(n)xO(nlogn + m) = O((n^2)logn + nm)
Of course, this requires that we build heaps and use them correctly.
First, seed the matrix with edges.
Then, update the matrix
for each Node, N, in the graph
cost(A,B) = min(cost(A,B), cost(A,N) + cost(N,B))
In something like C
for (int i = 0; i < n; i++)
for (int s = 0; s < n; s++)
for (int t = 0; t < n; t++)
cost[s,t] = min(cost[s,t], cost[s,i] + cost[i,t]);
Unfortunately, O(n^3)
Proof of correctness? Left to later.
This might also work with negative weights, provided you have no negative loops.
Reminder:
Casual: Given a connected, weighted, undirected graph, find a subset of edges that maintain connectedness and have the minimum sum of weights.
Quick survey: Who has seen/done this before?
Why care? (Concrete examples?)
Implementation strategies? (TPS)
Pairs, with assigned approaches
Be prepared to discuss next class
How do I determine if a graph is connected?
Search! O(n+m)
How do I determine if a connected graph has a cycle?
Count the number of edges. You need only n-1 edges for a cycle.
Write and present your algorithms.
Can we break any of these algorithms?
Can we argue/prove any of these correct?
We probably won’t get to this.
We probably won’t get to this.