Last active
January 10, 2021 15:14
-
-
Save pervognsen/92fb17fef5e978ebe18e55895cc86ee6 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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