Question

Apply Dijkstra's algorithm as discussed in class to solve the single-source shortest-paths problem for the following graph. Consider node A to be the source. (20 points) a. Show the completed table. b. State the shortest path from A to E and state its length. State the shortest path from A to F A 9 and state its length. d. State the shortest path from A to G 17 and state its length. 7 C. 12 B 8 10 D 8 2 4 E F 5 3 G

Answer 1

Dear student,

In Djikstra's Algorithm, we try to find the shortest path from one vertex to all other vertices using Greedy method.

First, we initialize all distances to infinity. Then, starting from the first vertex, we check all directly connected vertex. If the sum of cost comes less than the already assigned cost, we assign the smaller value. This way we traverse all the vertices, smallest first till we check all the vertices. The final values of all the vertices is the smallest possible cost path from the root vertex to those vertices individually.

Let us see the solution in detail below:

Given Graph:

여 it 5 No G 비 2. 12 u 으

a. Table:

T C DIE G Step selected Vertex B 2 B D 9 3 129 17 129 1160 117 12. 16 122 117 129 16 118 18117 12.9 16 118 117 16118 17 12 16. 18 17 4 20 5 6 E .G 9 2.0 12. 20

------------------------------------------------------------------------------------------------------------------------------------------

b. From the table we can see that,

The shortest path from A to E is:

A-C-D-E

Length: 18

​​​​​​​------------------------------------------------------------------------------------------------------------------------------------------

c. From the table we can see that,

The shortest path from A to F is:

A-C-F

Length: 17

​​​​​​​------------------------------------------------------------------------------------------------------------------------------------------

d. From the table we can see that,

The shortest path from A to G is:

A-C-F-G

Length: 20

------------------------------------------------------------------------------------------------------------------------------------------

I hope the given solution helps clear your doubt.

Don't forget to give it a thumbs up.

Regards