Assignment 5#
Dave Friedman
CMPSC 465 Data Structures and Algorithms
Summer 2024
1#
Consider the following directed graph.
A -> (B, 5), (C, 2)
B -> (C, 3), (E, 3), (F, 7)
C -> (B, 2), (D, 20)
D -> (E, 1)
E ->
F -> (E, 1), (G, 2)
G -> (H, 1)
H -> (D, 2)
A#
Treat the graph as unweighted and determine the single source shortest path distances from vertex B to all other vertexes within the graph using BFS. State explicitly the order in which nodes are visited as part of this search.
Mins
A -> inf
B -> 0, inf
C -> 1, inf
D -> 2, inf
E -> 1, inf
F -> 1, inf
G -> 2, inf
H -> 3, inf
Queue
(B, 0) <- pop(C, 1+0), (E, 1+0), (F, 1+0)
(C, 1) <- pop(E, 1), (F, 1), (B, 1+1), (D, 1+1)
(E, 1) <- pop(F, 1), (B, 2), (D, 2)
(F, 1) <- skip(B, 2), pop(D, 2), (E, 1+1), (G, 1+1)
(D, 2) <- skip(E, 2), pop(G, 2), (E, 1+2)
(G, 2) <- skip(E, 3), pop(H, 1+2)
(H, 3) <- (D, 1+3)
B -> C -> E -> F -> D -> G -> H
B#
Use the standard BFS algorithm (not Dijkstra’s) to calculate the path distances from vertex B to all other vertexes in the graph. Provide one example of a path between B and some other node that is shorter than the incorrect “shortest” path reported by the algorithm.
Mins
A -> inf
B -> 0, inf
C -> 3, inf
D -> 23, inf
E -> 3, inf
F -> 7, inf
G -> 9, inf
H -> 10, inf
Queue
(B, 0) <- pop(C, 3+0), (E, 3+0), (F, 7+0)
(C, 3) <- pop(E, 3), (F, 7), (B, 2+3), (D, 20+3)
(E, 3) <- pop(F, 7), (B, 5), (D, 23)
(F, 7) <- skip(B, 5), pop(D, 23), (E, 1+7), (G, 2+7)
(D, 23) <- skip(E, 8), pop(G, 9), (E, 1+23)
(G, 9) <- skip(E, 24), pop(H, 1+9)
(H, 10) <- (D, 2+10)
B -> C -> E -> F -> D -> G -> H
The weight of the path B -> F -> G -> H -> D is 12, which is less than the value from B to D reported by the algorithm.
C#
Perform Dijkstra’s algorithm to calculate the shortest path distances from vertex B to all other vertexes in the graph. State explicitly the order in which the nodes are visited.
Consider the following directed graph.
A -> (B, 5), (C, 2)
B -> (C, 3), (E, 3), (F, 7)
C -> (B, 2), (D, 20)
D -> (E, 1)
E ->
F -> (E, 1), (G, 2)
G -> (H, 1)
H -> (D, 2)
Mins
A -> inf
B -> 0, inf
C -> 3, inf
D -> 12, inf
E -> 3, inf
F -> 7, inf
G -> 9, inf
H -> 10, inf
Priority Queue
(B, 0) <- pop(C, 3+0), (E, 3+0), (F, 7+0)
(C, 3) <- pop(E, 3), (F, 7), (B, 2+3), (D, 20+3)
(E, 3) <- pop(F, 7), skip(B, 5), (D, 23)
(F, 7) <- (D, 23), skip(E, 1+7), pop(G, 2+7)
(G, 9) <- (D, 23), pop(H, 1+9)
(H, 10) <- (D, 23), pop(D, 2+10)
(D, 12) <- (D, 23), (E, 1+12)
B -> C -> E -> F -> G -> H -> D
2#
Consider the following directed acyclic graph.
A -> B, C
B -> C
C -> G
D -> E, F, K
E ->
F -> G, I
G -> H
H -> I
I ->
J ->
K -> I, J
A#
Identify all the sources and sinks in the graph.
A is a src
D is a src
E is a snk
I is a snk
J is a snk
B#
Draw a diagram of the reverse graph of the DAG.
A ->
B -> A
C -> A, B
D ->
E -> D
F -> D
G -> C, F
H -> G
I -> F, H, K
J -> K
K -> D
C#
Use DFS with timing, showing a table of the pre/post values, to produce a valid linearization of the DAG.
Pre Pst
A 11 12
B 13 14
C 10 15
D 2 3
E 1 4
F 6 7
G 9 16
H 8 17
I 5 20
J 21 22
K 18 19
Linearization
1. D -> E -> F -> A -> B -> C -> G -> H -> K -> I -> J
D#
State two more valid linearizations of the DAG.
Pre Pst
A 9 10
B 11 12
C 8 13
D 3 4
E 21 22
F 2 5
G 7 14
H 6 15
I 1 18
J 19 20
K 16 17
Linearization
1. D -> E -> F -> A -> B -> C -> G -> H -> K -> I -> J
2. D -> F -> A -> B -> C -> G -> H -> K -> I -> J -> E
Pre Pst
A 9 10
B 11 12
C 8 13
D 3 4
E 19 20
F 2 5
G 7 14
H 6 15
I 1 18
J 21 22
K 16 17
Linearization
1. D -> E -> F -> A -> B -> C -> G -> H -> K -> I -> J
2. D -> F -> A -> B -> C -> G -> H -> K -> I -> J -> E
3. D -> F -> A -> B -> C -> G -> H -> K -> I -> E -> J
In other words, E must follow D but otherwise has no ordering relation with any of the other nodes.
3#
Consider the single source shortest path problem on a directed graph \(G = (V, E)\) and a source vertex \(s \in V\) where each \(e \in E\) has a weight \(w(e)\). There are no cycles in the graph containing a negative weighted edge, and the only negative weighted edges are those leaving \(s\), i.e.
\(\forall(u, v \in E, u \ne s) \quad w((u, v)) \gt 0\)
Given these assumptions, will Dijkstra’s algorithm fail when run on this graph? Prove your conclusion.
Yes! Although \(G\) may be cyclic, that \(s\) is not involved in a cycle follows from the two requirements that edges outgoing from \(s\) are negative and that no cycles contain negative edges. Let there be \(k\) outgoing edges \((s, v_1), \dotsc, (s, v_k)\) such that \(w((s, v_1)) \le \dotsc \le w((s, v_k))\). Dijkstra’s algorithm begins by prioritizing \(v_1\), the vertex with the smallest weight, and proceeds as normal along subsequent nonnegative edges. Since the weight of the outgoing edge to \(v_1\) is smaller than the weights of any other outgoing edge, there is no path from \(s\) to \(v_1\) with a better path weight than the weight of the outgoing edge to \(v_1\) itself. And in general, for each \(v_i, v_j\) such that \(i \lt j\) there is no path from \(s\) to \(v_i\) through \(v_j\) with a better path weight than the weight of the outgoing edge to \(v_i\) itself. All this to say that Dijkstra’s algorithm proceeds no differently than it would if there were only nonnegative edges.
4#
Design an algorithm which accepts a directed graph as input and determines if there is a vertex within the graph from which all other vertexes are reachable. The algorithm should run in \(\Theta(|V| + |E|)\) time and you must demonatrate this fact.
The algorithm to determine whether a graph has exactly one source node, which depends on computing the in-degree of each vertex in the graph, requires \(\Theta(|V| + |E|)\) time.
INPUT a graph G = (V, E)
OUTPUT whether G has exactly one source node or not
HAS_SINGLE_SOURCE(G)
1 in_degree = {} // empty associative array
2
3 foreach u in V // for every vertex `u` in G...
4 in_degree[u] = 0 // ...initialize the in_degree of vertex `u`
5 foreach (u, v) in E // for every outgoing edge of vertex `u`...
6 in_degree[v] += 1 // ...increment the in_degree of vertex `u`
7
8 return 0 if exactly one else -1
Run DFS with timing to determine the cyclicity of \(G\). DFS with timing requires \(\Theta(|V| + |E|)\) time.
In the cyclic case, generate the strongly-connected component metagraph (or DAG) of \(G\) and then check that it has exactly one source node. Generating the strongly-connected component metagraph of \(G\) requires \(\Theta(|V| + |E|)\) time and checking whether it has exactly one source node requires \(\Theta(|V| + |E|)\) time.
In the acyclic case, check that \(G\) has exactly one source node.
\( \Theta(|V| + |E|) = \begin{cases} \underbrace{\Theta(|V| + |E|)}_{\text{cyclicity}} + \underbrace{\Theta(|V| + |E|)}_{\text{has\_single\_source}} + \underbrace{\Theta(|V| + |E|)}_{\text{metagraph}} & \text{directed cyclic graph} \\ \underbrace{\Theta(|V| + |E|)}_{\text{cyclicity}} + \underbrace{\Theta(|V| + |E|)}_{\text{has\_single\_source}} & \text{DAG} \\ \end {cases} \)