Algorithm-undirected graph

Let G = (V, E) be an undirected graph and each edge e ∈ E is associated with a positive weight ℓ(e). For simplicity we assume weights are distinct. Is the following statement true or false? Let P be the shortest path between two nodes s, t. Now, suppose we replace each edge weight ℓ(e) with ℓ(e)^2, then P is still a shortest path between s and t. search SEARCH ASK MATH SOLVER Database System ConceptsFIND Database System Concepts 7th Edition ISBN: 9780078022159 Author: Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan Publisher: McGraw-Hill Education bookmark_border 1 Introduction expand_moreChapter 1 : Introduction Chapter Questions expand_moreSection: Chapter Questions Problem 1PE format_list_bulletedProblem 1PE See similar textbooks Question Let G = (V, E) be an undirected graph and each edge e ∈ E is associated with a positive weight ℓ(e). For simplicity we assume weights are distinct. Is the following statement true or false? Let P be the shortest path between two nodes s, t. Now, suppose we replace each edge weight ℓ(e) with ℓ(e)^2, then P is still a shortest path between s and t. SAVE bookmark_border Expert Solution Check Mark arrow_forward Step 1 The statement is true. Step 2 To prove this, let us first assume that there exists a shorter path Q between s and t after replacing the edge weights with their squares. Here we will try to show you that this presumption leads to a contradiction. Let Q = (v_0, v_1, ..., v_k) be a path between s and t with total weight W(Q) after replacing edge weights with their squares, where v_0 = s and v_k = t. Since the weights are distinct and positive, we know that each edge has a distinct square weight as well. Therefore, W(Q) = ∑(i=1 to k) ℓ(v_{i-1},v_i)^2. Let P = (u_0, u_1, ..., u_m) be the shortest path between s and t in the original graph with total weight W(P), where u_0 = s and u_m = t. Since P is the shortest path, we know that W(P) ≤ W(Q). Now, let us construct a new path R by replacing each edge in P with a sequence of edges whose weights are their squares. Formally, for each edge (u_{i-1},u_i) in P, we add a new sequence of vertices and edges (u_{i-1}, w_{i,1}, w_{i,2}, ..., w_{i,k_i-1}, u_i), where the weight of each new edge (w_{i,j-1}, w_{i,j}) is the square of the original edge weight ℓ(u_{i-1}, u_i), and k_i is the number of edges in this sequence. Note that R is a path in the new graph with weight W(R) = ∑(i=1 to m) ∑(j=1 to k_i-1) ℓ(u_{i-1}, u_i)^2 = ∑(i=1 to m) (k_i-1) ℓ(u_{i-1}, u_i)^2. Since the weights are distinct and positive, we know that each edge in P has a distinct square weight as well. Therefore, W(R) is a sum of distinct terms, one for each edge in P, and each term is greater than or equal to the corresponding term in W(P). Now, let us compare W(R) and W(Q). Since each edge weight in Q is squared, we can write W(Q) as ∑(i=1 to k) √(ℓ(v_{i-1},v_i))^4 = ∑(i=1 to k) ℓ(v_{i-1},v_i)^2. Therefore, W(R) ≤ W(P) ≤ W(Q). However, we also know that Q is shorter than P in the new graph, which implies that W(Q) < W(R). This contradicts our previous inequality, and thus we have proven that the assumption of a shorter path Q after replacing edge weights with their squares leads to a contradiction. Therefore, the original statement is true: if P is the shortest path between s and t in the original graph, then P is still the shortest path between s and t after replacing edge weights with their squares.

Algorithm

Given a directed graph with non-negative edge weights, suppose we have computed the shortest paths from a given source to all the other vertices. If we modify the graph in such a way that the weights of all the edges are doubled, then, the shortest paths remain the same and only the total weights of the paths change. 1.True 2.False solution: a) True The given statement is true. Given a weighted graph with non negative edges, and a shortest path from source to all the other vertex, if we double the weight of the edges, the shortest path remains same, only total path weight changes. It is because weight of all path gets multiplied by same amount. Here the number of edges in a path doesn't matter, as just the weight is replaced on each path at fixed ratio.

GATE Syllabus 2019 for Computer Science and Information Technology

---

GATE Syllabus 2019 for Computer Science and Information Technology Candidates can check the syllabus of GATE 2019 for Computer Science and Information Technology given below. By knowing the syllabus, the candidates will be able to know which chapters and topics have to be studied or not.

• Section 1 – Engineering Mathematics
• Discrete Mathematics
Probability
• Linear Algebra
• Calculus
• Probability

• Section 2 – Digital Logic

• Section 3 – Computer Organization and Architecture

• Section 4 – Programming and Data Structures

• Section 5 – Algorithms

• Section 6 – Theory of Computation

• Section 7 – Compiler Design

• Section 8 – Operating System

• Section 9 – Databases

• Section 10 – Computer Networks