Page

$7.($Extra credit: $15$ points$)$ Dijkstra's algorithm for finding shortest paths.

Run Dijkstra's algorithm on the graph below to find a shortest path from source node $h$ to each vertex in the graph. For simplicity we use a distance array rather than a priority queue. Label each tree edge by the order in which it was selected. Use the table below to show the contents in the two arrays $D($for distance$)$ and $P($for parent vertex$)$ after each update.