Please enable JavaScript.

Coggle requires JavaScript to display documents.

Dijkstra's Algorithm - Coggle Diagram

- - - - Graph:
        
        Weighted
        
        Connected
      - Find shortest paths to all
        its other vertices.
- - - - Then....
        
        selects the vertex with the smallest such sum
      - To facilitate the algorithm’s operations:
        
        label each vertex with two labels
        
        The numeric label d indicates the length of the shortest path from the source to this vertex found by the algorithm so far
        
        when a vertex is added to the tree, d indicates the length of the shortest path from the source to that vertex
        
        The other label indicates the name of the next-to-last vertex on such a path(, the parent of the vertex in the tree being constructed.)
        
        After we have identified a vertex u∗ to be added to the tree:
        
        (1)-Move u∗ from the fringe to the set of tree vertices
        
        (2)-For each remaining fringe vertex u that is connected to u by an edge of weight w(u,u) such that u** +w(u,u)<du, update the labels of u by u, and du* +w(u,u), respectively