Dijkstra's Algorithm

Dijkstra's Algorithm

1. The shortest-paths problem is a very popular object of study

   • Some applications are:
     • The most widely used applications are transportation planning and packet routing in communication networks, including the Internet.
     • Another applications include finding shortest paths in social networks, speech recognition, document formatting, robotics, compilers, and airline crew scheduling.
     • In the world of entertainment, one can mention pathfinding in video games and finding best solutions to puzzles using their state-space graphs
   • The Dijkstra's algorithm is applicable to undirected and directed graphs with nonnegative weights only.
     • It 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
           • These vertices, the source, and the edges of the shortest paths leading to them from the source form a subtree Ti of the given graph
         • Since all the edge weights are nonnegative, the next vertex nearest to the source can be found among the vertices adjacent to the vertices of Ti.
           • The set of vertices adjacent to the vertices in Ti can be referred to as “fringe vertices”
             • they are the candidates from which Dijkstra’s algorithm selects the next vertex 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 and the length dv of the shortest path from the source to v
         • The sum is given by the weight of the edge (v, u) and the length is previously determined by the algorithm
         • Then, selects the vertex with the smallest such sum.
           • To facilitate the algorithm’s operations, we 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, i.e., the parent of the vertex in the tree being constructed.
                 • With such labeling, finding the next nearest vertex u∗ becomes a simple task of finding a fringe vertex with the smallest d value
                   • The labeling and mechanics of Dijkstra’s algorithm are quite similar to those used by Prim’s algorithm
                     • Both of them construct an expanding subtree of vertices by selecting the next vertex from the priority queue of the remaining vertices.
                       • They solve different problems and therefore operate with priorities computed in a different manner
             • After we have identified a vertex u∗ to be added to the tree, we need to perform two operations:
               • Move u∗ from the fringe to the set of tree vertices.
               • For each remaining fringe vertex u that is connected to u∗ by an edge of weight w(u∗, u) such that du∗ + w(u∗, u) < du, update the labels of u by u∗ and du∗ + w(u∗, u), respectively.
               • The time efficiency of Dijkstra’s algorithm depends on the data structures used for implementing the priority queue and for representing an input graph itself.

Imágenes y archivos del mapa