The shortest paths by using Dijkstra’s algorithm of the given graph. Definition used: Dijkstra algorithm is a step-by-step procedure for finding the shortest path in a weighted graph between two vertices. This algorithm enables to find shortest distances and the least cost, making it a valuable tool. Calculation: The given graph is as follows: Consider the number of vertices n, edges ( i , j ) and length l i j . In order to calculate the shortest path of the given graph by using the Dijkstra’s algorithm the following steps are taken as: Step1: Vertex 1 gets permanent length ( PL ): L 1 = 0 and Vertices j ( = 2 , ⋅ ⋅ ⋅ , n ) , L ˜ 2 = 2 , L ˜ 3 = 6 , L ˜ 4 = 8 , L ˜ 5 = ∞ and temporary length ( TL ): L ˜ j = l 1 j ( = ∞ if there is no edge ( 1 , j ) in G ) . Set P L = { 1 } , T L = { 2 , 3 , 4 , 5 } . Step 2: Fixing a permanent label. To calculate the value of k in T L for which L ˜ k is minimum. Therefore L 2 = 2 is minimum, then L 2 = min ( L ˜ 2 , L ˜ 3 , L ˜ 4 , L ˜ 5 ) = 2 hence the value of k = 2 . Since the value of P L = { 1 , 2 } and T L = { 3 , 4 , 5 } . Step 3: Updating temporary labels. For all j in T L , set L ˜ j = min k { L ˜ j , L k + l j k } therefore L ˜ 3 = min ( 6 , 2 + 3 ) = { 6 , 5 } = 5 , L ˜ 4 = min ( 8 , 2 + 7 ) = { 8 , 9 } = 8 and L ˜ 5 = min ( ∞ , 2 + ∞ ) = { ∞ , ∞ } = ∞ . Again, repeat the step 2 until the T L found empty. Thus L 3 = min ( L ˜ 3 , L ˜ 4 , L ˜ 5 ) = 5 hence the value of k = 3 . Since the value of P L = { 1 , 2 , 3 } and T L = { 4 , 5 } . For all j in T L , set L ˜ j = min k { L ˜ j , L k + l j k } therefore L ˜ 4 = min ( 8 , 5 + 5 ) = { 8 , 10 } = 8 , and L ˜ 5 = min ( ∞ , 5 + ∞ ) = { ∞ , ∞ } = ∞ . Again, repeat the step 2 until the T L found empty. Thus L 4 = min ( L ˜ 4 , L ˜ 5 ) = 8 hence the value of k = 4 . Since the value of P L = { 1 , 2 , 3 , 4 } and T L = { 5 } . Again, repeat the step 3 until the T L found empty. For all j in T L , set L ˜ j = min k { L ˜ j , L k + l j k } therefore, L ˜ 5 = min { ∞ , 8 + 20 } = { ∞ , 28 } = 28 . Again, repeat the step 2 until the T L found empty. Thus L 5 = min ( L ˜ 5 ) = 28 hence the value of k = 5 . Hence, the value of L 5 = 28 , k = 5 and the value of P L = { 1 , 2 , 3 , 4 , 5 } , T L = { ϕ } . Therefore, the resulting paths, of lengths L 2 = 2 , L 3 = 5 , L 4 = 8 , L 5 = 28 . Hence, figure 1 shows the resulting shortest paths of lengths L 2 = 2 , L 3 = 5 , L 4 = 8 , L 5 = 28 .

Question

Want to see the full answer?

Answer 1

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Students have asked these similar questions

Draw the isoclines with their direction markers and sketch several solution curves, including the curve satisfying the given initial conditions. 1) y'=x + 2y ; y(0) = 1 and 2) y' = x², y(0)=1

part b

Consider the following model of a population in continuous time. N(t) = rN(t)e¯ß³N(t), r > 0,ẞ> 0. (1) (a) Without solving the equation, determine an upper bound for N(t) in terms of the initial popu- lation No, and the parameters ẞ and r.