Thread: discrete math: graph theory

can plz help me with this question?

The answer is 4, the path followed is A-B-E-D.

If it is the algorithm you do not understand then I’ll give you the steps (Steps applied to your diagram are in brackets).

Step 1: Label the start vertex as 0 (so label A as 0).

Step 2: Box this number (Box the 0, this is a permanent box).

Step 3: Label each vertex that is connected to the start vertex with its distance (these may get crossed out as you find shorter routes so it is a temporary label) So B is 2 and F is 3 and D is 10.

Step 4: Box the smallest number (The 2 connecting A and B should get boxed).

Step 5: From this vertex, consider the distance to each connected vertex. (The path A-B- C overall is 8 so put an 8 above the C; however the distance from A-B-E is 3).

Step 6: If this distance is less than a distance already at this vertex, cross out this distance and write in the new distance. If there was no distance at the vertex write down the new distance).

Step 7: Repeat from step 4 until the destination vertex is boxed. (E-D is the shortest distance so the final path is ABED).

thanks for the help