Solve for X in the graph and matrix below

The following picture shows a graph, G G , with vertices V = A , B , C , D , E V = {A, B, C, D, E} with edge set E E . Some edge weights are shown, and others are not.

Also below is the resulting matrix D D from the Floyd-Warshall algorithm . In this matrix, D [ i ] [ j ] D[i][j] shows the distance between vertex i i and vertex j j in the graph. Solve for X X .

Graph and distance matrix Graph and distance matrix


The answer is 2.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Kyle Smida
Jun 21, 2020

Using the provided matrix we can see the distance from D to C is 5 and the only path is D=>E=>C, and the distance from E to C is 3. If the total distance from D to C is 5 and the distance from E to C is 3, then X has to be 2.

Hussain Safwan
Aug 28, 2018

The answer is available from the first row. Take respectively the nodes B, C and D as intermediate nodes to reach E from A and the respective distances stand to be 10+X for B, 24+X for C and 5+X for D, out of which 5+X is the minimum distance, hence 5+x must be equal to 7(the given minimum distance from A to E) and here you have it! x=7-5=2 :-)

Shourya Pandey
Nov 6, 2017

The only way to go from A A to D D without repeating edges is to take the edge from A A to D D , so that the edge A D A \rightarrow D has weight 5 5 . Similarly, the edge C B C \rightarrow B has weight 4 4 . Finally, the two real choices from A A to C C is to either take the direct edge, or to go via A D E C A \rightarrow D \rightarrow E \rightarrow C . The direct edge has cost 12 12 , which does not match the given matrix. Thus the shortest path from A A to C C is A D E C A \rightarrow D \rightarrow E \rightarrow C , which has cost 5 + x + 3 = 10 5 + x + 3 = 10 . Thus x = 2 {\bf x = 2} .

Simply look at the distance (D,C) = 5. Given (E,C) = 3. Thus, (D,E) = x = 2.

Dvora Levitan - 3 years, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...