next up previous
Next: About this document ...

CS130N Problem set 8: Weighted graphs

Discuss with your friends the similarity of the proofs of correctness of Dijkstra's, Kruskal's and Prim's algorithms. Abstract out the main steps of proof of correctness of any greedy algorithm.
Reconstruct the proof of correctness of the Bellman-Ford algorithm discussed in the class.
Given an example of an n-vertex graph G that causes Dijkstra's algorithm to run in $\Omega(n^2 \log{n})$ time.
Give an example of a weighted directed graph G with negative-weight edges, but no negative-wight cycle, such that Dijkstra's algorithm incorrectly computes the shortest path distance.
How is the Bellman-Ford algorithm able to work with negative weights?
In Dijkstra's algorithm, when we add a new weight z to C, let w be a node not in C. Is it possible that the new shortest special path from the source to w should pass first by z and then by some other node of C?
What can you say about the time required by Kruskal's algorithm if, instead of providing a list of edges, the user supplies a matrix of distances, leaving to algorithm the job of working out which edges exist?
Show that if all the weights in a connected graph G are distinct, then there is exactly one minimum spanning tree for G.
The problem of finding a subset T of the edges of a connected graph G such that all nodes remain connected when only the edges of T are used, and the sum of weights of edges in T is as small as possible, still makes sense even if G has edges with negative weights. However, the solution may no longer be a tree. Adapt either Kruskal's or Prim's algorithm to work on a graph that may include negative weights.
Suppose you are given a timetable, which consists of: Give an efficient algorithm for the following problem:

Given airports a and b, and a time t, find a sequence of flights that allows one to arrive at the earliest possible time in b when departing from a at or after time t. Minimum connecting time at intermediate airports should be observed.

Design an efficient algorithm for finding a longest directed path from a vertex s to a vertex t of an acyclic weighted digraph G. Specify the graph representation used and any auxiliary data structures used. Analyze the time complexity of your algorithm.

next up previous
Next: About this document ...
Subhashis Banerjee