sec shortest-paths problems figure an example graph for topological sort seven tasks have dependencies as shown by the directed graph we can also implement topological sort using queue instead of recursion to do sowe first visit all edgescounting the number of edges that lead to each vertex ( count the number of prerequisites for each vertexall vertices with no prerequisites are placed on the queue we then begin processing the queue when vertex is taken off of the queueit is printedand all neighbors of (that isall vertices that have as prerequisitehave their counts decremented by one any neighbor whose count is now zero is placed on the queue if the queue becomes empty without printing all of the verticesthen the graph contains cycle ( there is no possible ordering for the tasks that does not violate some prerequisitethe printed order for the vertices of the graph in figure using the queue version of topological sort is figure shows an implementation for the queue-based topological sort algorithm shortest-paths problems on road mapa road connecting two towns is typically labeled with its distance we can model road network as directed graph whose edges are labeled with real numbers these numbers represent the distance (or other cost metricsuch as travel timebetween two vertices these labels may be called weightscostsor distancesdepending on the application given such grapha typical problem is to find the total length of the shortest path between two specified vertices this is not trivial problembecause the shortest path may not be along the edge (if anyconnecting two verticesbut rather may be along path involving one or more intermediate vertices for examplein figure the cost of the path from to to is the cost of the edge directly from to is the cost of the path from to to to is thusthe shortest path from to is (not along the edge connecting to dwe use the notation (ad to indicate that the shortest distance from to is in figure there is no path from to bso we set (ebwe define (ad to be the weight of edge (ad)that