![]()
Visiting guest. Why not sign in?
|
|
|
Single Source AlgorithmsAs the concept of single source algorithms was only glossed over in the previous page, it needs to be explored in more detail before moving on to a specific implementation. Essentially, the solution to a single source shortest path problem on a graph G is a list of n-1 paths and their respective lengths. The most convenient, and a succinct representation of this solution is a minimum spanning tree. This is a tree data-structure containing all the nodes of the graphs, and only the edges needed for the shortest paths. ![]() Shortest paths can be built by reverse traversal of the tree, starting from the end point and moving towards the root. The length of that path can either be cached, or computed during the traversal. RelaxationThis is not a Zen meditation technique, but a procedure that is applied to the graph to form a minimum spanning tree. Essentially, each edge is scanned iteratively. If its end node is further than its start node plus the length of the path, then we update the information stored at that node. This involves resetting the parent node, and changing the distance. In C++ pseudo-code, this looks a bit like this: // root node assumed valid Node* root; // reset all the nodes' information for (Node* n = nodes.begin(); n != nodes.end(); n++) { n->distance = MAX_FLOAT; n->parent = root; } // set properties of root node root->distance = 0.0; root->parent = NULL; // start relaxation algorithm while (!graph.isSpanningTree()) { // scan all the edges in the graph for (Edge* e = edges.begin(); e != edges.end(); e++) { const float d = e->start->distance + e->length; // check if distance using this path is better if (e->end->distance > d) { // if so, update the end node e->end->distance = d; e->end->parent = e->start; } } } Depending on how your graph is laid out in memory, this algorithm can be more or less efficient. At the worst, however, it takes a whopping O(2^m) computation time. That's to be expected from naïve implementations, and that leaves a lot of room for better algorithms... PrototypesDijkstra was one of the first to really make his mark in the field, by formalising the problem and proposing his initial solution in 1959. This set the premise for a great number of successors, all of which improve the original performance. The concepts behind all the algorithms have, however, been captured into a single "prototype" algorithm -- based on Gallo and Pallottino's work (1986). Such a prototype would have this appearance: /** * Initialise all nodes and the root as in relaxation algorithm above. */ // create the working list of nodes vector<Node*> temporary; temporary.push_back( root ); // start shortest-path algorithm while (!temporary.empty()) { // fetch the next node to be scanned Node* node = Select( &temporary ); // scan all the edges of this node for (Edge* e = node->edges.begin(); e != node->edges.end(); e++) { const float d = e->start->distance + e->length; // check if distance using this path is better if (e->end->distance > d) { // if so, update the end node e->end->distance = d; e->end->parent = e->start; // this node needs to be processed by the algorithm too Insert( &temporary, e->end ); } } } The key points lie obviously in the unexplained Select and Insert procedures. In what order do we select the nodes? And how do we store the nodes for efficient insertion and removal? That's what it's all about, and looking into Dijkstra's approach will enlighten us with the first technique used. Dijkstra's AlgorithmDijkstra's algorithm uses a greedy approach to the node selection; the closest node to the root is selected next. This is known as a best first approach. If this is respected throughout, and if the path-lengths are always positive, then once a node is removed it does not need to be processed again -- ever. This property was discovered by Dijkstra, and implemented as such (note that the Insert is not needed): /** * Same initialisation as prototype algorithm above. */ while (!temporary.empty()) { // fetch the next node to be scanned Node* node = DeleteMin( &temporary ); // scan all the edges of this node for (Edge* e = node->edges.begin(); e != node->edges.end(); e++) { const float d = e->start->distance + e->length; // check if distance using this path is better if (e->end->distance > d) { // if so, update the end node e->end->distance = d; e->end->parent = e->start; } } } ImprovementsIn the initial implementation, the DeleteMin procedure used a linear scan of a list of nodes. This was of computational complexity O(n), providing a simple implementation. No doubt Dijkstra has identified this issue, and considered the upgrade to a more suited data-structure trivial ;) In following work, Johnson and Dial respectively used d-Heaps and buckets to reduce this complexity notably. Any reasonable data-structure will allow an efficient enough implementation on modern computers, so try to keep things simple Remember you can visit the Message Store to discuss this tutorial. There are already 6 replies in the thread, why not join in? Back to the Artificial Intelligence Depot.
|