Please enable JavaScript.

Coggle requires JavaScript to display documents.

Dijkstra's Algorithm - Coggle Diagram

- - - - Dijkstra’s algorithm finds the shortest paths to a graph’s vertices in order of their distance from a given source. First, it finds the shortest path from the source to a vertex nearest to it, then to a second nearest, and so on
        
        In general, before its ith iteration commences, the algorithm has already identified the shortest paths to
        i − 1 other vertices nearest to the source
        
        To identify the ith nearest vertex, the algorithm computes, for every fringe vertex u,
        the sum of the distance to the nearest tree vertex v (given by the weight of the edge (v, u)) and the length dv of the shortest path from the source to v
        (previously determined by the algorithm) and then selects the vertex with the smallest such sum
        
        The fact that it suffices to compare the lengths of such special paths is the
        central insight of Dijkstra’s algorithm