Q$3.$ Graph Shortest Path $-$ Dijkstra's algorithm $[25$ marks$].$

A directed weighted graph $G_3$ is shown in Fig. $3.$ We assume that the weight of the

edges represents the distance between two nodes. Please answer the following two

questions: $($i$)$ With $v1$ as the source, show how Dijkstra's algorithm works $($needs to

keep the predecessor of each node$)$ by completing the forwarding table for $v1$ as follows;

$($ii$)$ list the shortest path from $v1$ to $v6$ and its distance.

Here, $S$ represents the set of nodes that have been visited and included in the path, $d(v$#$)$

is the current distance from the source node $v1$ to every node $v$# in the graph, and $P(v$#$)$

represents the predecessor node in the shortest path between the source node $v1$ and

the node $v$#$.$

Fig. $3.$ A directed weighted graph $G_3.$