FACTOID # 10: The total number of state executions in 2005 was 60: 19 in Texas and 41 elsewhere. The racial split was 19 Black and 41 White.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Dijkstra's algorithm
Graph search algorithms
Search

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1959,[1] is a graph search algorithm that solves the single-source shortest path problem for a graph with non negative edge path costs, outputting a shortest path tree. This algorithm is often used in routing. Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. ... In computer science, A* (pronounced A star) is a graph/tree search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). ... The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). ... Best-first search is a search algorithm which optimizes breadth-first search by expanding the most promising node chosen according to some rule. ... Bidirectional search is a graph search algorithm that runs two simultaneous searches: one forward from the initial state, and one backward from the goal, and stopping when the two meet in the middle. ... In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... In Computer Science Depth-limited search is an algorithm to explore the Vertices of a Graph. ... In computer science, the Floyd–Warshall algorithm (sometimes known as the Roy–Floyd algorithm, since Bernard Roy described this algorithm in 1959) is a graph analysis algorithm for finding shortest paths in a weighted, directed graph. ... Hill climbing is a graph search algorithm where the current path is extended with a successor node which is closer to the solution than the end of the current path. ... Iterative deepening depth-first search or IDDFS is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches , the depth of the shallowest goal state. ... Johnsons algorithm is a way to solve the all-pairs shortest path problem in a sparse, weighted, directed graph. ... In computer science, uniform-cost search (UCS) is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph. ... Computer science (informally: CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. ... Edsger Dijkstra Edsger Wybe Dijkstra (Rotterdam, May 11, 1930 – Nuenen, August 6, 2002; IPA: ) was a Dutch computer scientist. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ... This article just presents the basic definitions. ... A shortest path tree is a tree, in Graph Theory, that is constructed so that the distance between a root node and all other nodes is minimum. ... This article is about routing in computer networks. ...


For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined. For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. This article just presents the basic definitions. ...

Contents

Algorithm

It should be noted that distance between nodes can also be referred to as weight.

  1. Create a distance list, a previous vertex list, a visited list, and a current vertex.
  2. All the values in the distance list are set to infinity except the starting vertex which is set to zero.
  3. All values in visited list are set to false.
  4. All values in the previous list are set to a special value signifying that they are undefined, such as null.
  5. Current vertex is set as the starting vertex.
  6. Mark the current vertex as visited.
  7. Update distance and previous lists based on those vertices which can be immediately reached from the current vertex.
  8. Update the current vertex to the unvisited vertex that can be reached by the shortest path from the starting vertex.
  9. Repeat (from step 6) until all nodes are visited.

..


Lay descriptions of the algorithm

Suppose you create a knotted web of strings, with each knot corresponding to a node, and the strings corresponding to the edges of the web: the length of each string is proportional to the weight of each edge. Now you compress the web into a small pile without making any knots or tangles in it. You then grab your starting knot and pull straight up. As new knots start to come up with the original, you can measure the straight up-down distance to these knots: this must be the shortest distance from the starting node to the destination node. The acts of "pulling up" and "measuring" must be abstracted for the computer, but the general idea of the algorithm is the same: you have two sets, one of knots that are on the table, and another of knots that are in the air. Every step of the algorithm, you take the closest knot from the table and pull it into the air, and mark it with its length. If any knots are left on the table when you're done, you mark them with the distance infinity.


Or, using a street map, suppose you're marking over the streets (tracing the street with a marker) in a certain order, until you have a route marked in from the starting point to the destination. The order is conceptually simple: from all the street intersections of the already marked routes, find the closest unmarked intersection - closest to the starting point (the "greedy" part). It's the whole marked route to the intersection, plus the street to the new, unmarked intersection. Mark that street to that intersection, draw an arrow with the direction, then repeat. Never mark to any intersection twice. When you get to the destination, follow the arrows backwards. There will be only one path back against the arrows, the shortest one.


Pseudocode

In the following algorithm, u := extract_min(Q) searches for the vertex u in the vertex set Q that has the least dist[u] value. That vertex is removed from the set Q and returned to the user. length(u, v) calculates the length between the two neighbor-nodes u and v. alt on line 10 is the length of the path from the root node to the neighbor node v if it were to go through u. If this path is shorter than the current shortest path recorded for v, that current path is replaced with this alt path. The previous array is populated with a pointer to the "next-hop" node on the source graph to get the shortest route to the source.

 1 function Dijkstra(Graph, source): 2 for each vertex v in Graph: // Initializations 3 dist[v] := infinity // Unknown distance function from source to v 4 previous[v] := undefined 5 dist[source] := 0 // Distance from source to source 6 Q := copy(Graph) // All nodes in the graph are unoptimized - thus are in Q 7 while Q is not empty: // The main loop 8 u := extract_min(Q) // Remove and return best vertex from nodes in two given nodes // we would use a path finding algorithm on the new graph, such as depth-first search. 9 for each neighbor v of u: // where v has not yet been removed from Q. 10 alt := dist[u] + length(u, v) 11 if alt < dist[v] // Relax (u,v) 12 dist[v] := alt 13 previous[v] := u 14 return previous[] 

If we are only interested in a shortest path between vertices source and target, we can terminate the search at line 9 if u = target. Now we can read the shortest path from source to target by iteration:

 1 S := empty sequence 2 u := target 3 while defined previous[u] 4 insert u at the beginning of S 5 u := previous[u] 

Now sequence S is the list of vertices constituting one of the shortest paths from source to target, or the empty sequence if no path exists.


A more general problem would be to find all the shortest paths between source and target (there might be several different ones of the same length). Then instead of storing only a single node in each entry of previous[] we would store all nodes satisfying the relaxation condition. For example, if both r and source connect to target and both of them lie on different shortest paths through target (because the edge cost is the same in both cases), then we would add both r and source to previous[target]. When the algorithm completes, previous[] data structure will actually describe a graph that is a subset of the original graph with some edges removed. Its key property will be that if the algorithm was run with some starting node, then every path from that node to any other node in the new graph will be the shortest path between those nodes in the original graph, and all paths of that length from the original graph will be present in the new graph. Then to actually find all these short paths between two given nodes we would use a path finding algorithm on the new graph, such as depth-first search.


Running time

The running time of Dijkstra's algorithm on a graph with edges E and vertices V can be expressed as a function of |E| and |V| using the Big-O notation. For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ...


The simplest implementation of the Dijkstra's algorithm stores vertices of set Q in an ordinary linked list or array, and operation Extract-Min(Q) is simply a linear search through all vertices in Q. In this case, the running time is O(|V|2+|E|)=O(|V|2).


For sparse graphs, that is, graphs with many fewer than |V|2 edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a binary heap, pairing heap, or Fibonacci heap as a priority queue to implement the Extract-Min function efficiently. With a binary heap, the algorithm requires O((|E|+|V|) log |V|) time (which is dominated by O(|E| log |V|) assuming every vertex is connected, i.e., |E||V| - 1), and the Fibonacci heap improves this to O( | E | + | V | log | V | ) amortized time. In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ... In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list. ... Example of a complete binary max heap. ... Pairing heaps are a type of heap data structure with relatively simple implementation, excellent practical amortized performance (particularly for applications where heaps must be merged). ... In computer science, a Fibonacci heap is a data structure similar to a binomial heap but with a better amortized running time. ... A priority queue is an abstract data type in computer programming, supporting the following three operations: add an element to the queue with an associated priority remove the element from the queue that has the highest priority, and return it (optionally) peek at the element with highest priority without removing... In computer science, a Fibonacci heap is a data structure similar to a binomial heap but with a better amortized running time. ... In computational complexity theory, amortized analysis is the time per operation averaged over a worst_case sequence of operations. ...


Related problems and algorithms

The functionality of Dijkstra's original algorithm can be extended with a variety of modifications. For example, sometimes it is desirable to present solutions which are less than mathematically optimal. To obtain a ranked list of less-than-optimal solutions, the optimal solution is first calculated. A single edge appearing in the optimal solution is removed from the graph, and the optimum solution to this new graph is calculated. Each edge of the original solution is suppressed in turn and a new shortest-path calculated. The secondary solutions are then ranked and presented after the first optimal solution.


Dijkstra's algorithm is usually the working principle behind link-state routing protocols, OSPF and IS-IS being the most common ones. A link-state routing protocol is one of the two main classes of routing protocols used in packet-switched networks for computer communications. ... Open Shortest Path First (OSPF) is a link-state, hierarchical Interior Gateway Protocol (IGP) routing protocol. ... Is Is is Yeah Yeah Yeahs third EP, to be released on July 24, 2007. ...


Unlike Dijkstra's algorithm, the Bellman-Ford algorithm can be used on graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s. (The presence of such cycles means there is no shortest path, since the total weight becomes lower each time the cycle is traversed.) The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). ...


The A* algorithm is a generalization of Dijkstra's algorithm that cuts down on the size of the subgraph that must be explored, if additional information is available that provides a lower-bound on the "distance" to the target. The A* search algorithm (pronounced A star) is a graph search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). ...


The process that underlies Dijkstra's algorithm is similar to the greedy process used in Prim's algorithm. Prim's purpose is to find a minimum spanning tree for a graph. Prims algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ... The minimum spanning tree of a planar graph. ...


References

  1. ^ E. W. Dijkstra: A note on two problems in connexion with graphs. In Numerische Mathematik, 1 (1959), S. 269–271.

Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002); IPA: ) was a Dutch computer scientist. ... Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

See also

Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. ... A link-state routing protocol is one of the two main classes of routing protocols used in packet-switched networks for computer communications. ... Open Shortest Path First (OSPF) is a link-state, hierarchical Interior Gateway Protocol (IGP) routing protocol. ... Is Is is Yeah Yeah Yeahs third EP, to be released on July 24, 2007. ... Prims algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ...

External links


  Results from FactBites:
 
CodingForums.com - Dijkstras ALgorithm.. (482 words)
Dijkstra's searches through a graph of nodes and edges mimicing stations and lines so it appeared to be the best solution.
Dijkstra's algorithm is, in fact, a good choice for a solution(any faster has proven to be impossible to date).
When this algorithm terminates, the labels of all vertices are the shortest paths from v to that vertex.
5.7.1 Dijkstra Algorithm (286 words)
his algorithm finds the routes,by cost precedence.Let's assume that every cost is a positive number,and assume the same in the cost function c as in 5.4 paragraph.
G may be a graph,a digraph,or even a combined one,which means that only some of its sides are directed.If we consider G as digraph,then every other case is fully covered as well since a no directed side can be considered a 2 directed sides of equal cost for every direction.
he idea for this algorithm is based on the fact that every m.r containing more than one side is the expansion of another m.r.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m