notes best example of -heap is "djikstra' algorithmdjikstra' algorithm (named after its discoverdutch computer scientist dijkstrasolves the problem of finding the shortest path from point in graph (the sourceto destination with non-negative weight edge it turns out that one can find the shortest paths from given source to all vertices (pointsin graph in the same time hencethis problem is sometimes called the single-source shortest paths problem dijkstra' algorithm is greedy algorithmwhich finds shortest path between all pairs of vertices in the graph before describing the algorithms formallylet us study the method through an example figure directed graph with no negative edge( dijkstra' algorithm keeps two sets of verticess is the set of vertices whose shortest paths from the source have already been determined - is the set of remaining vertices the other data structures needed ared array of best estimates of shortest path to each vertex from the source pi an array of predecessors for each vertex predecessor is an array of vertices to which shortest path has already been determined the basic operation of dijkstra' algorithm is edge relaxation if there is an edge from to vthen the shortest known path from to can be extended to path from to by adding edge ( ,vat the end this path will have length [ ]+ ( ,vif this is less than [ ]we can replace the current value of [vwith the new value the predecessor list is an array of indicesone for each vertex of graph each vertex entry contains the index of its predecessor in path through the graph operation of algorithm the following sequence of diagrams illustrate the operation of dijkstra' algorithm the bold vertices indicate the vertex to which shortest path has been determined initialize the graphall the vertices have infinite costs except the source vertex which has zero cost lovely professional university