Description
1. Consider the following graph, with node 0 as the source node.
(a) Run Dijkstra’s algorithm. Write down the d array before each EXTRACT-MIN, also the final array.
(b) Run Bellman-Ford algorithm. Write down the d distance array after each pass.
2. Run the Floyd-Warshall algorithm on the following graph. Show the matrix D(k)
that results for each
iteration of the outer loop.
3. Let G(V, E) be a directed, weighted graph. The goal is to find the shortest path from a source node s
to every nodes in the graph.
(a) If all edges have unit weight, is there an algorithm faster than Dijkstra? Please just state the
algorithm and its running time.
(b) Now suppose the weight function has the form w(·) : E → {1, 2}, i.e. every edge has weight either 1
or 2. Design O(|V | + |E|)-time algorithm for the problem. Please show why your algorithm works
and how to get the running time bound.
4. The goal of this problem is to travel from home to a store, purchase a gift, and then get back home, at
minimal cost.
Let us model this problem using a directed graph. Let G(V, E) be a directed, weighted graph, with
non-negative edge weights w : E → R
+. The weight of an edge represents the cost of traversing that
edge. Each vertex v ∈ V also has an associated cost c(v) ∈ R
+ which represents the cost of purchasing
the desired gift at that location.
Starting from “home base” h ∈ V , the goal is to find a location v ∈ V where the gift can be purchased,
along with a path p from h to v and back from v to h. The cost of such a solution is the cost c(v) of the
location v plus the weight w(p) of the path p (i.e., the sum of edge weights along the path p).
Design an algorithm that on input G(V, E), including edge weights w(·) and costs c(·), and home base
h ∈ V , finds a minimal cost solution. Assuming G is represented using adjacency lists, and Dijkstra’s
algorithm runs in O(|E| log |V |). Your algorithm should run Dijkstra exactly once and in time O((|V |+
|E|) log |V |). Please show why your algorithm works and analyze the time complexity.
Hints: If you try to solve with the original graph G, then most likely you will have to run multiple times
of Dijkstra. You can try to extend the graph G into two layers. What is the number of nodes and edges?
