– Batman gives you an undirected, unweighted, connected graph G = (V, E) with |V| = n, |E| =…

Question:

Transcribed Image Text:

–

Batman gives you an undirected, unweighted, connected graph G = (V, E) with |V| = n, |E| = m, and

two vertices s, te V.

He wants to know dist(s, t) given that the edge (u, v) is destroyed, for each edge (u, v) € E. In other

words, for each (u, v) € E, he wants to know the distance between s and t in the graph G’ = (V’, E’),

where E’

E{(u, v)}.

Some constraints:

= The dist definition and notation used is the same as that in lectures.

● It is guaranteed that t is always reachable from s using some sequence of edges in E, even after any

edge is destroyed.

• To help you, Batman gives you an n x n matrix Mnxn. You have to update M[u, v] to contain the

value of dist (s, t) if the edge (u, v) is destroyed, for each (u, v) E E.

• You can assume that you are provided the edges in adjacency list representation.

The edge (u, v) is considered the same as the edge (v, u).

(a) (12 points) Batman expects an algorithm that works in O(V|· (|V| + |E|) = O(n · (n + m)).

(b) (4 points) He also wants you to provide him with proof of runtime of your algorithm, i.e., a Time-

Complexity Analysis of the algorithm you provide.

(c) (4 points) Lastly, you also need to provide proof of correctness for your algorithm. –

Batman gives you an undirected, unweighted, connected graph G = (V, E) with |V| = n, |E| = m, and

two vertices s, te V.

He wants to know dist(s, t) given that the edge (u, v) is destroyed, for each edge (u, v) € E. In other

words, for each (u, v) € E, he wants to know the distance between s and t in the graph G’ = (V’, E’),

where E’

E{(u, v)}.

Some constraints:

= The dist definition and notation used is the same as that in lectures.

● It is guaranteed that t is always reachable from s using some sequence of edges in E, even after any

edge is destroyed.

• To help you, Batman gives you an n x n matrix Maxn. You have to update M[u, v] to contain the

value of dist (s, t) if the edge (u, v) is destroyed, for each (u, v) E E.

• You can assume that you are provided the edges in adjacency list representation.

The edge (u, v) is considered the same as the edge (v, u).

(a) (12 points) Batman expects an algorithm that works in O(V|· (|V| + |E|) = O(n · (n + m)).

(b) (4 points) He also wants you to provide him with proof of runtime of your algorithm, i.e., a Time-

Complexity Analysis of the algorithm you provide.

(c) (4 points) Lastly, you also need to provide proof of correctness for your algorithm. –

Batman gives you an undirected, unweighted, connected graph G = (V, E) with |V| = n, |E| = m, and

two vertices s, te V.

He wants to know dist(s, t) given that the edge (u, v) is destroyed, for each edge (u, v) € E. In other

words, for each (u, v) € E, he wants to know the distance between s and t in the graph G’ = (V’, E’),

where E’

E{(u, v)}.

Some constraints:

= The dist definition and notation used is the same as that in lectures.

● It is guaranteed that t is always reachable from s using some sequence of edges in E, even after any

edge is destroyed.

• To help you, Batman gives you an n x n matrix Mnxn. You have to update M[u, v] to contain the

value of dist (s, t) if the edge (u, v) is destroyed, for each (u, v) E E.

• You can assume that you are provided the edges in adjacency list representation.

The edge (u, v) is considered the same as the edge (v, u).

(a) (12 points) Batman expects an algorithm that works in O(V|· (|V| + |E|) = O(n · (n + m)).

(b) (4 points) He also wants you to provide him with proof of runtime of your algorithm, i.e., a Time-

Complexity Analysis of the algorithm you provide.

(c) (4 points) Lastly, you also need to provide proof of correctness for your algorithm.

Expert Answer:

Answer rating: 100% (QA)

To solve this problem we can use Dijkstra s algorithm to find the shortest path between s and t in the original graph G However since we need to compu

View the full answer