1. Consider a directed graph with distinct and non-negative edge
lengths and a source vertex s.
Fix a destination vertex t, and assume that the graph contains at
least one s-t path. Which of the
following statements are true? [Check all that apply.]
( )The shortest (i.e., minimum-length) s-t path might have as many
as n−1 edges, where n is the number of vertices.
( )There is a shortest s-t path with no repeated vertices (i.e., a
"simple" or "loopless" such path).
( )The shortest s-t path must include the minimum-length edge of
G.
( )The shortest s-t path must exclude the maximum-length edge of
G.
1. Consider a directed graph with distinct and non-negative edge
lengths and a source vertex s.
Fix a destination vertex t, and assume that the graph contains at
least one s-t path. Which of the
following statements are true? [Check all that apply.]
( )The shortest (i.e., minimum-length) s-t path might have
as many as n−1 edges, where n is the number of
vertices.
Answer:
This choice is correct, consider the graph that is simply a chain from $ s $ to $ t $, it must go through all vertices.
( )There is a shortest s-t path with no repeated vertices (i.e., a "simple" or "loopless" such path)
Answer:
This choice is correct - but it is not immediately obvious how
can one claim this fact, especially so the problem statement does
not imply the graph is finite (am I thinking too much?).
Denote the set of $ s - t $ path *lengths* be $ \mathbf{L} $. Now $
\mathbf{L} $ is a set of integer and therefore there is a minimum
value $ m $ by Archimedean Principle. Therefore the set $ \{ p : p
\in \mathbf{L} and length(p) = m \} $ is not empty and any path in
the set is a shortest path.
Suppose the contrary that such a path has one or more loop, we can
remove the loop. That cannot reduce the path length because that
path is already shortest (i.e. every edge in the loop has to be 0
length). Therefore the path with one less loop must be also in the
set, inductively the set must have a path without any loops.
( )The shortest s-t path must include the minimum-length edge of G.
Answer:
This is incorrect. Consider the graph
s - 10 -> t
s - 3 -> u
u - 8 -> t
The shortest path from $ s $ to $ t $ is the direct path, and it
does not include the minimum length edge
( )The shortest s-t path must exclude the maximum-length
edge of G.
Answer:
This is also incorrect. Consider the graph
s - 10 -> t
There is only one path and therefore the edge is also the maximum
edge and cannot be excluded.
1. Consider a directed graph with distinct and non-negative edge lengths and a source vertex s....
Consider a directed acyclic graph G = (V, E) without edge lengths and a start vertex s E V. (Recall, the length of a path in an graph without edge lengths is given by the number of edges on that path). Someone claims that the following greedy algorithm will always find longest path in the graph G starting from s. path = [8] Ucurrent = s topologically sort the vertices V of G. forall v EV in topological order do...
Given a directed graph with positive edge lengths and a specified vertex v in the graph, the "all-pairs" v-constrained shortest path problem" is the problem of computing for each pair of vertices i and j the shortest path from i to j that goes through the vertex v. If no such path exists, the answer is . Describe an algorithm that takes a graph G= (V; E) and vertex v as input parameters and computes values L(i; j) that represent...
Algorithm Question 5. Below is a graph with edge lengths. Apply Dijkstra's algorithm to find the shortest paths, starting at vertex A, to all other vertices. Write down the sequence in which the edges are chosen, breaking ties by using vertices at the same length in alphabetic orde. 3 Ga 2 5. Below is a graph with edge lengths. Apply Dijkstra's algorithm to find the shortest paths, starting at vertex A, to all other vertices. Write down the sequence in...
Say that we have an undirected graph G(V, E) and a pair of vertices s, t and a vertex v that we call a a desired middle vertex . We wish to find out if there exists a simple path (every vertex appears at most once) from s to t that goes via v. Create a flow network by making v a source. Add a new vertex Z as a sink. Join s, t with two directed edges of capacity...
Run Dijkstra's algorithm on the graph G below, where s is the source vertex. Draw a table that shows the vertices in Q at each iteration. Write thed and I values of each vertex. Color the edges in the shortest-path tree, similar to the example from the notes. List the order in which vertices are added to S. Use the algorithm learned in class.
Input a simple undirected weighted graph G with non-negative edge weights (represented by w), and a source node v of G. Output: TDB. D: a vector indexed by the vertices of G. Q: priority queue containing the vertices of G using D[] as key D[v]=0; for (all vertex ut-v) [D[u]-infinity:) while not Q. empty() 11 Q is not empty fu - Q.removein(); // retrieve a vertex of Q with min D value for (all vertex : adjacent to u such...
Run the Dijkstra’s algorithm on the directed graph of the following figure 24.6, using vertex t as the source. In the style of Figure 24.6, show the d and ? values and the vertices in set S after each iteration of the while loop. 1 8 10 I 10 14 4 6 4 6 2 3 2 3 4 6 5 5 2 (a) (c) 1 10 13 4 6 (d) (e) Figure 24.6 The execution of Dijkstra's algorithm. The...
10. You are given a directed graph G(V, E) where every vertex vi E V is associated with a weight wi> 0. The length of a path is the sum of weights of all vertices along this path. Given s,t e V, suggest an O((n+ m) log n) time algorithm for finding the shortest path m s toO As usual, n = IVI and m = IEI.
a. (15 marks) i (7 marks) Consider the weighted directed graph below. Carry out the steps of Dijkstra's shortest path algorithm as covered in lectures, starting at vertex S. Consequently give the shortest path from S to vertex T and its length 6 A 2 3 4 S T F ii (2 marks) For a graph G = (V, E), what is the worst-case time complexity of the version of Dijkstra's shortest path algorithm examined in lectures? (Your answer should...
Exercise 5. Let G be a graph in which every vertex has degree at least m. Prove that there is a simple path (i.e. no repeated vertices) in G of length m.