2 3 5 Consider the weighted graph above. Start from vertex a and use Prim\'s alg
ID: 3146219 • Letter: 2
Question
2 3 5 Consider the weighted graph above. Start from vertex a and use Prim's algorithm to create a minimal spanning tree. Give the edges added in order Start with the cheapest edges and use Kruskal's algorithm to create a minimal spanning tree. Give the edges added in order Use Dijkstra's algorithm to create the tree that makes the shortest paths from a to all other vertices. Vertices in the path: length of path: 1 a to b: Vertices in the path: a, C length of path:-- length of path:-2 length of path:-3 length of path:_4 length of path:-8 a to c a to d: Vertices in the path a, b, d a to e: Vertices in t a,b,c a to Vertices in the path: a, C,T a to g: Vertices in the path: a, d, gExplanation / Answer
Prims:
1) start from vertex a go to b
2) choose the cheapest available edge attached to any previously chosen vertex:
cost(a,c) =3 cost(b,d) =1 .....minimum
cost(a,d)=3 cost(b,e) =2
thus we select minimum cost edge from b to d.
3) Again continuing the same process of choosin the cheapest available edge attached to any previously chosen vertex avoiding any cycle formation:
cost(a,c) =3 cost(b,e) =2....minimum
cost(d,g) =5 cost(d,f) =4 we neglect a to d due to cycle formation.
Thus we select minimum cost egde from b to e.
4) continuing the same process:
cost(e,g) =8 cost(a,c) =3....minimum
cost(d,g) =5 cost(d,f) =4
Thus we select minimum cost egde from a to c.
5) continuing the same process:
cost(e,g) =8 cost(c,f) =1....minimum
cost(d,g) =5 cost(d,f) =4
Thus we select minimum cost egde from c to f
6). continuing the same process:
cost(d,g) =5 cost(d,f) =4
cost(f,g) =5 cost(e,g) =8
here we get two equal cost edges ie cost(f,g) = cost(d,g) = 5 . so we can take any of the two edges which will result in formation of two different minimum spanning trees.
Krushals's:
1)start from vertex a to b.
2)choose the cheapest available edge anywhere which does not violate the goal of creating a spanning tree i.e no cycle or loop is formed .
cost(b,e) = 2 cost(e,g) =8 cost(a,d) =3
cost(a,c) = 3 cost(d,g) =5 cost(d,f) =4
cost(f,g) =5 cost(b,d) =1 cost(c,f) = 1
here we get two minimum egedes: cost(b,d) = cost(c,f) = 1 select any one out of the two.
thus we select minimumedge from c to f.
3)choose the cheapest available edge anywhere without forming any cycle
cost(b,e) = 2 cost(e,g) =8 cost(a,d) =3
cost(a,c) = 3 cost(d,g) =5 cost(d,f) =4
cost(f,g) =5 cost(b,d) =1(minimum)
out of all available edges select the minimum of all.thus we select minimum edge from b to d
4)choose the cheapest available edge anywhere without forming any cycle
cost(b,e) = 2(minimum) cost(e,g) =8 cost(a,d) =3
cost(a,c) = 3 cost(d,g) =5 cost(d,f) =4
cost(f,g) =5
out of all available edges select the minimum of all.thus we select minimum edge from b to e
5)choose the cheapest available edge anywhere without forming any cycle
cost(e,g) =8 cost(a,d) =3(neglect because it will form a cycle)
cost(a,c) = 3(minimum) cost(d,g) =5 cost(d,f) =4
cost(f,g) =5
out of all available edges select the minimum of all.thus we select minimum edge from a to c
6)choose the cheapest available edge anywhere without forming any cycle
cost(e,g) =8 cost(d,g) =5 cost(d,f) =4(neglect because it will form a cycle) cost(f,g) =5
here we get two equal cost edges ie cost(f,g) = cost(d,g) = 5 . so we can take any of the two edges which will result in formation of two different minimum spanning trees.
Dijkstra:
there are some errors in your answers I am correcting them, rest are correct:
from a to e:
vertices are : a,b,e length of path : 3
from a to g:
vertices are : a,b,d,g length of path : 7
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.