Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A grid graph is a directed graph where the vertices are arranged in k rows each
containing k vertices, where k is a positive integer. Let v[i,j] denote the jth
vertex in the ith row. Let s = v[1,1]. A grid graph has the following vertices and edges:
V = {v[i,j] | 1 <= i <= k and 1 <= j <= k}
E = {(v[i,j], v[i,j+1]) | 1 <= i <= k and 1 <= j < k} union
{(v[i,j], v[i,j-1]) | 1 <= i <= k and 1 < j <= k} union
{(v[i,j], v[i+1,j]) | 1 <= i < k and 1 <= j <= k}
The below figure shows the grid graph for k = 5:
[See figure on last page of http://www.cs.au.dk/~gerth/dADS03/opgaver/s03.pdf. The
important thing to understand is that there are edges going in both directions horizontally
but vertically edges can only go upward.]
For the rest of this problem, we will assume all edges have non-negative weights.
Question A: Let n and m denote respectively the number of vertices and edges in a
grid graph. Express n and m as function of k.
Question B: What's the execution time of Dijkstra's algorithm to find the length of
the shortest paths from s = v[1,1] to all the other vertices in the grid graph, as a
function of k?
Question C: Describe an algorithm that finds the lengths of the shortest paths from
s = v[1,1] to all other vertices in a grid graph in time O(m). Prove the algorithm's
execution time and correctness.
A cylinder graph is a grid graph expanded with non-negatively weighted edges between
the leftmost and rightmost vertex in each row, i.e. E now also includes the edges
(v[i,1], v[i,k]) and (v[i,k], v[i,1]) for 1 <= i <= k.
Question D: Describe an algorithm that finds the lengths of the shortest paths from
s = v[1,1] to all other vertices in a cylinder graph in time O(m). Prove the algorithm's
execution time and correctness.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment