Dijkstra's algorithm
|
|
Dijkstra's algorithm, named after its inventor, Dutch computer scientist Edsger Dijkstra, is an algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights.
For example, if the vertices of the graph represent cities and edge weights represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between two cities.
The input of the algorithm consists of a weighted directed graph G and a source vertex s in G. We will denote V the set of all vertices in the graph G. Each edge of the graph is an ordered pair of vertices (u,v) representing a connection from vertex u to vertex v. The set of all edges is denoted E. Weights of edges are given by a weight function w: E -> [0, ∞]; therefore w(u,v) is the non-negative cost of moving from vertex u to vertex v. The cost of an edge can be thought of as (a generalization of) the distance between those two vertices. The cost of a path between two vertices is the sum of costs of the edges in that path. For a given pair of vertices s and t in V, the algorithm finds the path from s to t with lowest cost (i.e. the shortest path). It can also be used for finding costs of shortest paths from a single vertex s to all other vertices in the graph.
| Contents |
Description of the algorithm
The algorithm works by keeping for each vertex v the cost d[v] of the shortest path found so far. Initially, this value is 0 for the source vertex s and infinity for all other vertices, representing the fact that we do not know any path leading to those vertices. When the algorithm finishes, d[v] will be the cost of the shortest path from s to v or infinity, if no such path exists.
The basic operation of Dijkstra's algorithm is edge relaxation: if there is an edge from u to v, then the shortest known path from s to u can be extended to a path from s to v by adding edge (u,v) at the end. This path will have length d[u]+w(u,v). If this is less than d[v], we can replace the current value of d[v] with the new value.
Edge relaxation is applied until all values d[v] represent the cost of the shortest path from s to v. The algorithm is organized so that each edge (u,v) is relaxed only once, when d[u] has reached its final value.
The algorithm maintains two sets of vertices S and Q. Set S contains all vertices for which we know that the value d[v] is already the cost of the shortest path and set Q contains all other vertices. Set S starts empty, and in each step one vertex is moved from Q to S. This vertex is chosen as the vertex with lowest value of d[u]. When a vertex u is moved to S, the algorithm relaxes every outgoing edge (u,v).
Pseudocode
In the following algorithm, u := Extract-Min(Q) searches for the vertex u in the vertex set Q that has the least d[u] value. That vertex is removed from the set Q and then returned. Q := update(Q) updates the weight field of the current vertex in the vertex set Q.
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G] // Initialization
3 do d[v] := infinity
4 previous[v] := undefined
5 d[s] := 0
6 S := empty set
7 Q := set of all vertices
8 while Q is not an empty set
9 do u := Extract-Min(Q)
10 S := S union {u}
11 for each edge (u,v) outgoing from u
12 do if d[v] > d[u] + w(u,v) // Relax (u,v)
13 then d[v] := d[u] + w(u,v)
14 previous[v] := u
15 Q := Update(Q)
If we are only interested in a shortest path between vertices s and t, we can terminate the search at line 9 if u = t.
Now we can read the shortest path from s to t by iteration:
1 S := empty sequence 2 u := t 3 while defined u 4 do insert u to the beginning of S 5 u := previous[u]
Now sequence S is the list of vertices on the shortest path from s to t.
Implementations
C
#define INFINITY (MAX_INT - 1)
typedef struct {
int weight;
int dest;
} DijkEdge;
typedef struct {
DijkEdge* connections; /* An array of edges which has this as the starting node */
int numconnect;
int distance;
int isDead;
} Vertex;
void Dijkstra(Vertex* graph, int nodecount, int source) {
for(int i = 0; i < nodecount; i++) {
if(i == source) {
graph[i].distance = 0;
graph[i].isDead = 0;
} else {
graph[i].distance = INFINITY;
graph[i].isDead = 0;
}
}
for(int i = 0; i < nodecount; i++) {
int next;
int min = INFINITY+1;
for(int j = 0; j < nodecount; j++) {
if(!graph[j].isDead && graph[j].distance < min) {
next = j;
min = graph[j].distance;
}
}
for(int j = 0; j < graph[next].numconnect; j++) {
if(graph[graph[next].connections[j].dest].distance >
graph[next].distance + graph[next].connections[j].weight)
{
graph[graph[next].connections[j].dest].distance =
graph[next].distance + graph[next].connections[j].weight;
}
}
graph[next].isDead = 1;
}
for(int i = 0; i < nodecount; i++) {
printf("The distance between nodes %i and %i is %i",
source, i, graph[i].distance);
}
}
C++
#include <map>
#include <queue>
using namespace std;
#define X first
#define Y second
template <class Node, class Edge=int> class Dijkstra {
public:
Dijkstra() {}
Dijkstra(const Node &n, const Edge &e=0) { push(n, e); }
bool empty() const { return q.empty(); }
void push(const Node &n, const Edge &e=0) {
Iter it = m.find(n);
if (it == m.end()) it = m.insert(make_pair(n, e)).X;
else if (it->Y > e) it->Y = e;
else return;
q.push(make_pair(e, it));
}
const Node &pop() {
cur = q.top().Y;
do q.pop();
while (!q.empty() && q.top().Y->Y < q.top().X);
return cur->X;
}
const Edge &dist() const { return cur->Y; }
void link(const Node &n, const Edge &e=1) { push(n, cur->Y + e); }
private:
typedef typename map<Node, Edge>::iterator Iter;
typedef pair<Edge, Iter> Value;
struct Rank : public binary_function<Value, Value, bool> {
bool operator()(const Value& x, const Value& y) const {
return x.X > y.X;
}
};
map<Node, Edge> m;
priority_queue<Value, vector<Value>, Rank> q;
Iter cur;
};
// Example usage (nodes and edges are represented with ints)
int shortestDistance(int nodes, int startNode, int endNode, int **dists) {
Dijkstra<int> dijkstra(startNode);
while (!dijkstra.empty()) {
int curNode = dijkstra.pop();
if (curNode == endNode)
return dijkstra.dist();
for (int i = 0; i < nodes; i++)
if (dists[curNode][i] >= 0) // "i" is a neighbor of curNode
dijkstra.link(i, dists[curNode][i]); // add weighted edge
}
return -1; // No path found
}
Python
import sys
infinity = sys.maxint - 1
class Vertex(object):
"""A vertex in a graph, using adjacency list.
'edges' is a sequence or collection of tuples (edges), the first element of
which is a name of a vertex and the second element is the distance to that vertex.
'name' is a unique identifier for each vertex, like a city name, an integer, a tuple of coordinates..."""
def __init__(self, name, edges):
self.name = name
self.edges = edges
def ShortestPath(graph, source, dest):
"""Returns the shortest distance from source to dest, using Dijkstra's algorithm.
Assumes the graph is connected."""
distances = {}
names = {}
for v in graph:
distances[v.name] = infinity # Initialize the distances
names[v.name] = v # Map the names to the vertices they represent
distances[source.name] = 0 # The distance of the source to itself is 0
dist_to_unknown = distances.copy() # Select the next vertex to explore from this dict
last = source
while last.name != dest.name:
# Select the next vertex to explore, which is not yet fully explored and which
# minimizes the already-known distances.
next = names[ min( [(v, k) for (k, v) in dist_to_unknown.iteritems()] )[1] ]
for n, d in next.edges: # n is the name of an adjacent vertex, d is the distance to it
distances[n] = min(distances[n], distances[next.name] + d)
if n in dist_to_unknown:
dist_to_unknown[n] = distances[n]
last = next
if last.name in dist_to_unknown: # Delete the completely explored vertex
del dist_to_unknown[next.name]
return distances[dest.name]
Running time
We can express the running time of Dijkstra's algorithm on a graph with m edges and n vertices as a function of m and n using the Big O notation.
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 Θ(n2).
For sparse graphs, that is, graphs with much less than n2 edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a binary heap or Fibonacci heap as a priority queue to implement the Extract-Min function. With a binary heap, the algorithm requires Θ((m+n)log n) time, and the Fibonacci heap improves this to Θ(m + n log n).
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.
OSPF (open shortest path first) is a well known real-world implementation of Dijkstra's algorithm used in internet routing.
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.
A related problem is the traveling salesman problem, which is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start. This problem is NP-hard; in other words, unlike the shortest path problem, it is unlikely to be solved by a polynomial-time algorithm.
If additional information is available that estimates the "distance" to the target, the A* algorithm can be used instead to cut down on the size of the subset of the graph which is explored.
References
- E. W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269271
- Cormen, T. H.; Leiserson C. E.; & Rivest R. L. (1990) Introduction to Algorithms. MIT Press. ISBN 0-262-03141-8
External links
- Animation of Dijkstra's algorithm (http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html)
- Java Applet showing Dijkstra's algorithm step by step (http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm)
- Dijkstra's algorithm (http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html)
- Interactive Site showing Dijkstra's Algorithm (http://www.mcs.csuhayward.edu/~morgan/notes_CS4590/Dijkstra_SPF_Applet/)
- The Boost Graph Library (BGL). BGL follows the same ideas of STL but is specialized for working with graphs (http://www.boost.org/libs/graph/doc/index.html)de:Algorithmus von Dijkstra
es:Algoritmo de Dijkstra fr:Algorithme de Dijkstra he:אלגוריתם דייקסטרה nl:Kortste Pad Algoritme it:Algoritmo di Dijkstra ja:ダイクストラ法 pl:Algorytm Dijkstry pt:Algoritmo de Dijkstra