The undirected graph on vertices 0,…,4 has weight matrix W=pmatrix0&1&8&1&4\\1&0&12&4&9\\8&12&0&7&3\\1&4&7&0&2\\4&9&3&2&0pmatrix. Find the shortest path weight from vertex 1 to vertex 2 using at most three edges.

GATE 2010 CS (CS1) – Question 61

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

The undirected graph on vertices 0,…,4 has weight matrix $$W=\begin{pmatrix}0&1&8&1&4\\1&0&12&4&9\\8&12&0&7&3\\1&4&7&0&2\\4&9&3&2&0\end{pmatrix}.$$ Find the shortest path weight from vertex 1 to vertex 2 using at most three edges.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) 8

Explanation

A three-edge path 1→0→4→2 has weight 1+4+3=8. The unconstrained shortest route 1→0→3→4→2 weighs seven but uses four edges and is ineligible. Checking one-edge and two-edge routes gives at least eleven; other three-edge routes cannot improve eight. Thus B.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

GATE 2015 CS (CS2) Q47 – Match algorithms 1 Dijkstra shortest path, 2 Floyd–Warshall all-pairs shortest paths, 3…
GATE 2015 CS (CS3) Q55 – A connected undirected graph has 100 vertices and 300 edges. Its minimum spanning-tree…
GATE 2021 CS (CS2) Q11 – G is connected, undirected and weighted. S1: Some minimum-weight edge of G is present in…
GATE 2021 CS (CS2) Q56 – For the directed graph shown, which statements hold?
GATE 2021 CS (CS2) Q65 – In the DAG shown with source s, a path’s quality is the product of its edge weights. A…
GATE 2026 CS (CS1) Q41 – Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a…

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →