Running Time
An upper bound of the running time of Dijkstra's algorithm on a graph with edges and vertices can be expressed as a function of and using big-O notation.
For any implementation of vertex set the running time is in, where and are times needed to perform decrease key and extract minimum operations in set, respectively.
The simplest implementation of the Dijkstra's algorithm stores vertices of set in an ordinary linked list or array, and extract minimum from is simply a linear search through all vertices in . In this case, the running time is .
For sparse graphs, that is, graphs with far fewer than 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 extracting minimum efficiently. With a binary heap, the algorithm requires time (which is dominated by, assuming the graph is connected). To avoid O(|V|) look-up in decrease-key step on a vanilla binary heap, it is necessary to maintain a supplementary index mapping each vertex to the heap's index (and keep it up to date as priority queue changes), making it take only time instead. The Fibonacci heap improves this to .
Note that for directed acyclic graphs, it is possible to find shortest paths from a given starting vertex in linear time, by processing the vertices in a topological order, and calculating the path length for each vertex to be the minimum length obtained via any of its incoming edges.
Read more about this topic: Dijkstra's Algorithm
Famous quotes containing the words running and/or time:
“Even in harmonious families there is this double life: the group life, which is the one we can observe in our neighbour’s household, and, underneath, another—secret and passionate and intense—which is the real life that stamps the faces and gives character to the voices of our friends. Always in his mind each member of these social units is escaping, running away, trying to break the net which circumstances and his own affections have woven about him.”
—Willa Cather (1873–1947)
“A man was to live in that egg-shell day and night, a mile from the shore.... Think of making your bed thus in the crest of a breaker! To have the waves, like a pack of hungry wolves, eying you always, night and day, and from time to time making a spring at you, almost sure to have you at last.”
—Henry David Thoreau (1817–1862)