search
Log In
1 vote
261 views

in Algorithms
edited by
261 views
0
please..take the required portion of screen and upload it again :)
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?

Please help in understanding this statement
0
I also did the same...

1 Answer

0 votes
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

15 votes
1 answer
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 ______.
asked Sep 24, 2016 in Algorithms User007 1.1k views
1 vote
1 answer
2
1.1k views
Which of the following statements is true? Adding a constant to every edge weight in a directed graph can change the set of edges that belongs to minimum cost spanning tree. Assume unique weights. Complete graph with 4 vertices, each edges having same weights can have maximum ... no negative cycles). None of these how is 3rd wrong? If there is no negative cycles dijkstra can work just fine right?
asked Jan 20, 2017 in Algorithms Pankaj Joshi 1.1k views
1 vote
1 answer
3
5 votes
1 answer
4
1.2k views
What is the time complexity of Dijkstra’s algorithm if it is implemented using AVL Tree instead of Priority Queue over a graph G = (V, E)?
asked Nov 5, 2016 in Algorithms vaishali jhalani 1.2k views
...