chap graphs /compute shortest path distances from sstore them in static void dijkstra(graph gint sint[dfor (int = < () ++/initialize [iinteger max valued[ for (int = < () ++/process the vertices int minvertex(gd)/find next-closest vertex setmark(vvisited)if ( [ =integer max valuereturn/unreachable for (int first( ) () next(vw)if ( [ ( [vg weight(vw)) [wd[vg weight(vw)figure an implementation for dijkstra' algorithm the first method is simply to scan through the list of |vvertices searching for the minimum valueas followsstatic int minvertex(graph gint[dint /initialize to any unvisited vertexfor (int = < () ++if ( getmark( =unvisitedv ibreakfor (int = < () ++/now find smallest value if (( getmark( =unvisited&( [id[ ]) ireturn vbecause this scan is done |vtimesand because each edge requires constanttime update to dthe total cost for this approach is th(| | | |th(| | )because |eis in (| | the second method is to store unprocessed vertices in min-heap ordered by distance values the next-closest vertex can be found in the heap in th(log | |time every time we modify ( )we could reorder in the heap by deleting and reinserting it this is an example of priority queue with priority updateas described in section to implement true priority updatingwe would need to store with each vertex its array index within the heap simpler approach is to add the new (smallerdistance value for given vertex as new record in the heap the smallest value for given vertex currently in the heap will be found firstand greater distance values found later will be ignored because the vertex will already be marked as visited the only disadvantage to repeatedly inserting distance values is that it will raise the number of elements in the heap from th(| |to th(| |in the worst case the time complexity is th((| | |log | |)because for each edge we must reorder the heap because the objects stored on the heap need to