# MadeEasy Test Series: Algorithms - Graph Algorithms

1 vote
261 views edited
0
1
Updated:)
0
nothing special about it. we have to run Dijkstra on this graph and find out all shortest path costs : add them then minus $7$
0
I did it in similar way.The path from M to S has cost as 7.

But the parameter EMax,I have added all the edge wait that were included by dijakstra and i got 22 ,but in the solution they have added each vertex cost instead of edge cost. and they got 58-7 as answer where as i got 22-7 as answer.

Am i understansing it incorrect ?
0
$E_{max}$ is shortest distance from source vertex to every other vertex in the given graph but not dijkstras graph.
0
Lets consider vertex D and S,the shortest distance from M to D is 6 and M to S is 7.Will we add 6+7 to Emax for this,or will we add 1+5+1(Because this is the cost of all edges which shows shortest distance from M to vertex S and D).

I hope question is cleared.

The question says cost of all edges which shows shortest distance from M to all other vertex ,so we will ad tll the edge cost involved in Dijakstra graph?

0
I also did the same...

M-A = 1

M-E1=2

M-D=6

M-A1=3

M-S=7

M-E=8

M-Y=9

M-S1=10

M-C=12

hence the value of emax is sum of all these which is 58.

Minimum spaning tree cost is 40 so emax-esp= 58-18

40

Correct me I wrong .

## Related questions

1
1.1k views
For the graph given below Dijkstra’s algorithm does not provide correct shortest path tree. Suppose a new graph that is different only in weight between Q to S is created. The number of values of edge [Q to S] that ensures that Dijkstra’s provide the correct shortest path tree where the values of edge (Q to S) ∈ [–20, 20] and ‘P’ is the source vertex are ______.
1 vote
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????