Question

Question 5 (5 points) Apply Dijkstra's Algorithm to the following graph, computing the shortest path for al vertices from vertex A. Present the results after each vertex has been processed 3 20 B 47 20 You may wish to present the results in the format of the following table: Stage Current Vertex Labels and Distances A 0 A 0 D 231 A 213 E 4 F21 A 90 Each row states (a) the current stage, (b) the vertex just added to the search graph, and (c) the current updated predecessor node label and distance from A for each vertex in the graph. Any values given here in the table are merely for example, and do not correspond to the solution for this problem. The vertices should be processed in the order dictated by Dijkstra's Algorithm. Question 6 (5 points) Apply Dijkstra's Algorithm as in Question 5, once again providing the results at each stage, to the following directed graph: 19 B 3 5 12 16 As before, compute the shortest path for all vertices from vertex A

Answer 1

Please Note:
Following the HOMEWORKLIB RULES, I have answered the first Question. Please Re-Post for receiving answers on the other questions.

Q5.
Answer)
Dijkstra's Algorithm:

Calculating values from vertex A:

Vertex A:
A: 0
B: 20
C: 47

Accessing Vertex B:
A: 0
B: 20
C: 47
E: 27
D: 40

Accessing Vertex C:
A: 0
B: 20
C: 47
E: 27
D: 40
all are minimal

Accessing Vertex E:
A: 0
B: 20
C: 47 (20+7+20 is the same = 47)
E: 27
D: 30 (27+3)
F: 35 (27 + 8)

Shortest paths from A is:
A: 0
B: 20
C: 47
E: 27
D: 30
F: 35