Hence proved ... :p

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+21 votes

Consider a complete undirected graph with vertex set $\{0, 1, 2, 3, 4\}$. Entry $W_{ij}$ in the matrix $W$ below is the weight of the edge $\{i, j\}$

$$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}$$

What is the minimum possible weight of a path $P$ from vertex $1$ to vertex $2$ in this graph such that $P$ contains at most $3$ edges?

- $7$
- $8$
- $9$
- $10$

+20 votes

+9

Is there any shortcut method for determining the mini possible wt of a path from vertex 1 to 2.

Because if we take the brute force approach it is very time consuming .Moreover, there are chances of error as well.

+8

@vidhi ....we can apply bellman ford algorithms upto 3 iterations

Start from vertex 1 as source

i=1 representing atmost 1 edge

i=2 representing atmost 2 edge

i=3 representing atmost 3 edge

Use Bellman Ford only for vertex 2, to save time.....

+2

@gshivam

Using bellman ford is fine, but it is very time consuming.

As first we have to convert the undirected graph to a directed one https://cs.stackexchange.com/questions/24768/shortest-path-in-weightedpositive-or-negative-undirected-graph

And then apply Bellman ford from vertex 1 as src.

I tried as below ::(may be helpful to other readers)

But, can anyone suggest any other shortcut method??

+2

I tried the below approach and it worked!!

We want to reach vertex 2 from 1.

What now I do is, scan the adjacency matrix in a column-wise fashion and now I determine the shortest edge by which I can reach a **vertex i **in the graph.

Like, to reach vertex 2, I can reach with a minimum cost from vertex 4 with cost 3.

Following the similar pattern, I build a path tree, which goes from vertex 1 to vertex 2.

Now, this path from vertex 1 to 2 consist of 4 edges but I want a path with at most 3 edges.

So, now using vertex 1 as source and other vertices 0,3,2 I multiplex them one by one and check which one will give me the shortest path.

**And cost comes out to be 8.**

+29 votes

For getting quick answer just draw a tree of depth 3. And compare various path. Although it is brute force, But this method will not take much time.

+2

Why have you not expanded the last 1->4->0>2 and 1->4->3->2 ,although it is not shortest but why did you not find in the tree diagram?

+1

Why have you not expanded the last 1->4->0>2 and 1->4->3->2 ,although it is not shortest but why did you not find in the tree diagram?

@ rahul sharma 5 ji. Good point but while making tree i realized that they will not give minimum. But yes we can draw them also to make the diagram more elegant and clear.

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 590
- Exam Queries 575
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,397 questions

53,564 answers

185,727 comments

70,837 users