首页 > 代码库 > 最短路径--Dijkstra算法原理分析
最短路径--Dijkstra算法原理分析
1. What is problem we faced ?
/**
* Q: What is problem we faced ?
*
* A: In our life, there are many problems about pathfinding. Those problems can be simplified as a shorest
* path problem. In a words,we need to find a suitable path to arrive our destination in a map. For examples
* : In Internet, there are many routers work for us to transmit data. They are consist of a huge network.
* It is necessary to find a suitable path between arbitrary two nodes.In addition, this path must be dynamic
* since the huge network is always change.
*/
2. How can we solve it ? Any advices ?
/**
* Q: How can we solve it ? Any advices ?
*
* A: To solve this problem, I was try to find a method to do it. when I did, I found it is difficult to ensure
* my path is optimal, Although looks like. There are still possible exist a path that is more shorter than
* I‘s. Now, the problem is how can we ensure a path is optimal. That is not easy. But Dijkstra has been
* introduced a amazing method. Usually, we explore a new thing by analyze it basic principles first. But
* that is not always suitable.For this algorithm, we will try to explore it from the outside to the inside.
* First at all, we simple explain how we can get a shorest path. Then we will demonstrate it.
*/
3. How does Dijkstrate Algorithm work ?
/**
* Q: How does Dijkstrate Algorithm work ?
*
* workflow:
* 1). label the start point as visited and others as unvisit.
* 2). obviously, the distance from the start point to the start point is 0.
* 3). compute the distance between the start point and it‘s neighbor nodes.
* 4). choice the nearest node, label it as visited. and we can ensure it‘s path is shorest path.
* 5). compute the distance between start point and all of nodes which have at least one visited node as
* neighbor.
* 6). choice the nearest node, label it as visited.
* 7). return step(5) untill the new nearest node is destination.
* When we find destination, all of nodes,which has been labeled as visited , has been get the shorest path.
* Here has a Animation about this:
* http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html
*/
4. Why does it work ?
/**
* Q: Why does it work ?
*
* A: recall the steps above, there are two steps is suspicious. One,when we want to find the nearest node, we
* always check the neighbor node of visited node.But why the nearest node is reside in the neighbor nodes ?
* Two, when we found a "nearest node", why we can ensure a path is optimal by find nearest node ?
*/
5. why the nearest node is reside in the neighbor nodes ?
/**
* Q: why the nearest node is reside in the neighbor nodes ?
*
* A: First at all, we declare a words: nearest node, that is a node which have a nearest distance except for visited node.
*
* build three set: SV( set of visited nodes), SU( set of unvisited nodes), and NN(set of neighbor nodes). SV
* is used to contain all of nodes which has been visited. SU is used to contatin nodes which is unvisited.
* NN is set of nodes which is neighbor with at least one visited node. Assume that:
* s -- start point
* x -- a element of NN
* y -- a element of SV
* z -- a element of SU
* if we want to find a path to z.( s->...->z). The path must contain a node of NN. That means
* s->...->z.
* must belong to
* s->...->x ->...->z
* we can always know
* L(s->...->x) < L(s->...->x ->...->z) = L(s->...->z)
* So whatever we choice unvisited node and path, we can still find a more shorter path value in the
* neighbor node.
*/
6. why we can ensure a path is optimal by find nearest node ?
/**
* Q: why we can ensure a path is optimal by find nearest node ?
*
* A: As we analysis above, the nearest node must be the neighbor of a visited node.
* Now, at the example above ,Image we has been found a nearest node x, we can get this conclusion:
* L(s->...->x) = Min{ s->...->x} ---expr1
* That‘s means there is no path have a more shorter distance than L(s->...->x).
*
* If that is wrong, there are another path is more shorter. That must be
* L(s->...->x0->...->z->...->x) < L(s->...->x)
* (x0 is belong to NN, but not same with x)
* That‘s means
* L(s->...->x0) < L(s->...->x0->...->z->...->x) < L(s->...->x)
* !!!!!!
* L(s->...->x0) < L(s->...->x)
* that is impossible.
* So if we can find a nearest node ,then we can ensure the path is optimal.
*/
7. source code
/*** Here is an example*/#include <stdio.h>/** the distance of unneighborly nodes*/#define UNRN 99/** used to index to a array,based on 0*/typedef int INDEX;/** there are two status for a node.*/enum VISITSTAT{ L_UNVISIT, L_VISIT, L_INVALID,};class Dijkstra { public: Dijkstra( int map[], int e_num, int unre); ~Dijkstra( ); bool set( int start, int target); bool work( ); /* * show the value of distance of nodes. when a node has been labeled as visited. * this value represent the minimum distance. */ bool show(); /* * show the path from start point to destination. */ bool showPath( ); private: /* * when we label a new node as visited, we need to update the distance of * neighbor node. */ bool _UpdateRelDistanceTable(); /* * used to find the nearest node when we had update the distance value of * neighbor node. */ bool _GetNextNearest( INDEX &ind); int _mapNode( INDEX x, INDEX y); bool _mapLabel( INDEX x); bool _travel( INDEX cur);/*** To a node, three types of information is necessary: * 1). the relationship between this node with other nodes. Whether their are neighbor.* what is the distance between two nodes. * 2). the status of a node. Whether a node has been visited.* 3). the distance between the start node with the other nodes.*/ //relationship between nodes int *map; //status of those nodes VISITSTAT *ele_stat; //the distance int *ele_relds; //the number of the elements int ele_num; //start point INDEX start; //end point INDEX target; //the value of unrelated node. int unre;};Dijkstra::Dijkstra( int map[], int e_num, int unre){ this->map = map; this->ele_relds = new int[ e_num]; this->ele_stat = new VISITSTAT[e_num]; this->ele_num = e_num; this->start = 0; this->target = 0; this->unre = unre; /* * label all of nodes as unvisited */ for( int i=0; i<e_num; i++) this->ele_stat[i] = L_UNVISIT; /* * initialize the distance as unreachable */ for( int i=0; i <e_num; i++) this->ele_relds[i] = unre;}Dijkstra::~Dijkstra( ){ }/*** Logically, a map should be a two-dimensional array. But we can only build a * one-dimensional array because of some reasons. So, for convenience,we define * a function used to help us access the map.*/int Dijkstra::_mapNode( INDEX x, INDEX y){ return this->map[ this->ele_num* x + y];}bool Dijkstra::_mapLabel( INDEX x){ if( (x<0) || (x>=this->ele_num) ) return false; this->ele_stat[x] = L_VISIT; return true;}bool Dijkstra::set( INDEX start, INDEX target){ this->start = start; this->target = target; return true;}/*** the core function, used to realize the algorithm.*/bool Dijkstra::work( ){ /* * first at all, we label the start node as visited and initialize the distance between this node * with the start point. Obviously, it is 0. */ INDEX cur = this->start; this->ele_relds[cur] = 0; this->_mapLabel( cur); /* * we compute the distance of neighbor nodes and find the nearest node periodically. * Untill find the nearest node is destination, we get the shortest path to the destination. */ do { //update the related distance of visited node this->_UpdateRelDistanceTable( ); //get the nearest node and label it as visited if( !this->_GetNextNearest( cur)) { return false; } this->_mapLabel( cur); } while( cur!=this->target); return true;}bool Dijkstra::show(){ INDEX i; printf(" %d-->%d\n", this->start, this->target); for( i=0; i<this->ele_num; i++) { printf("[%d] %4d\n", this->ele_stat, this->ele_relds[i]); } return true;}/*** Actually, we didn't save information about the shorest path. But ,with the help of the* information of shorest distance, we can still deduce the right path reversely.*/bool Dijkstra::showPath( ){ INDEX cur = this->target; this->_travel( cur); return true;}/*** As we all know, all of the shorest distance of visited nodes is resolved. So* if we want to find the right path of a node, we just need to ensure :* the shorest distance of current node is equal to the sum of the shorest distance* of neighbor node and its' path.* */bool Dijkstra::_travel( INDEX cur){ if( cur==this->start) { printf("%d\n", cur); return false; } printf(" %d->", cur); INDEX i; for( i=0; i<this->ele_num; i++) { //find neighbor if( this->_mapNode( cur, i)!=this->unre ) { //find right path if((i!=cur) &&(this->ele_relds[cur]==this->ele_relds[i] + this->_mapNode( cur, i)) ) { this->_travel( i); } } } return true;}bool Dijkstra::_UpdateRelDistanceTable( ){ INDEX i; for( i=0; i<this->ele_num; i++) { //find those nodes visited if( this->ele_stat[i] == L_VISIT) { INDEX j; for( j=0; j<this->ele_num; j++) { //find those nodes which is neighboor to the visited node and unvisited if( (this->_mapNode( i, j)!=this->unre) &&(this->ele_stat[j])==L_UNVISIT ) { //compute related distance int rel_ds = this->ele_relds[i]+ this->_mapNode( i, j); //update related distance if( rel_ds<this->ele_relds[j] ) this->ele_relds[j] = rel_ds; } } } } return true;}bool Dijkstra::_GetNextNearest( INDEX &ind){ INDEX min = -1; INDEX i; for( i=0; i<this->ele_num; i++) { //find those nodes visited if( this->ele_stat[i]==L_VISIT) { INDEX j; for( j=0; j<this->ele_num; j++) { //find nodes which is neighboor and unvisited if( (this->_mapNode( i, j)!=this->unre) &&(this->ele_stat[ j]==L_UNVISIT) ) { if( ( min == -1) ||(this->ele_relds[j]<this->ele_relds[min])) { min = j; } } } } } ind = min; return ind==-1?false:true;}#define E_NUM 8// O A B C D E F Tstatic int Map[ E_NUM*E_NUM] = {/* O*/ 0, 2, 5, 4, UNRN, UNRN, UNRN, UNRN, /* A*/ 2, 0, 2, UNRN, UNRN, UNRN, 12, UNRN,/* B*/ 5, 2, 0, 1, 4, UNRN, UNRN, UNRN,/* C*/ 4, UNRN, 1, 0, UNRN, 4, UNRN, UNRN,/* D*/ UNRN, UNRN, 4, UNRN, 0, 1, UNRN, 5,/* E*/ UNRN, UNRN, UNRN, 4, 1, 0, UNRN, 7,/* F*/ UNRN, 12, UNRN, UNRN,UNRN, UNRN, 0, 3,/* T*/ UNRN, UNRN, UNRN, UNRN,5, 7, 3, 0,};static int UnreNode = UNRN;int main(){ Dijkstra map( Map, E_NUM, UnreNode); map.set( 0, 7); map.work( ); map.show(); map.showPath(); return 0;}
最短路径--Dijkstra算法原理分析