<- People Behind Informatics


All 0-9 A B C D E F G H I J K L M N O P Q R S T U V W XY Z




 
Shortest Path Algorithm
Dijkstra's algorithm is probably the best-known and thus most implemented shortest path algorithm. It is simple, easy to understand and implement, yet impressively efficient. Djikstra's algorithm solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is sometimes called the single-source shortest paths problem. To describe Dijkstra’s algorithm in an intuitive way we use the following definitions: • Every path in a weighted digraph has an associated path weight, the value of which is the sum of the weights of that path’s edges. • A shortest path between two vertices s and t in such a graph is a directed simple path from s to t with the property that no other such path has a lower weight. • Given a network and a designated vertex s, a shortest-paths tree (SPT) for s is a subnetwork containing s and all the vertices reachable from s that forms a directed tree rooted at s such that every tree path is a shortest path in the network. To compute a SPT we begin by putting the source on the SPT; then, we build the SPT one edge at a time, always taking next the edge that gives a shortest path from the source to a vertex not on the SPT. In other words, we add vertices to the SPT in order of their distance (through the SPT) to the start vertex. This method is known as Dijkstra's algorithm. One has to make a distinction between the algorithm at the level of abstraction in the informal description (given above) and various concrete implementations that differ primarily in graph representation and priority-queue implementations. Furthermore, Dijkstra's algorithm solves the single-source shortest -path problem in networks that have nonnegative (!) weights. [Source: Robert Sedgewick, Algorithms in C++, Part 5 Graph Algorithms, Addison-Wesley, 2002]
 

 

<- People Behind Informatics


Home  |  Top  |  Search  |  Gallery  | Glossary  | Sitemap  |  Making Of  |  Help