面对现实,超越自己
逆水行舟,不进则退
posts - 269,comments - 32,trackbacks - 0

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。

Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。

其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

初始时,S中仅含有源。设u是G的某一个顶点,把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中,同时对数组dist作必要的修改。一旦S包含了所有V中顶点,dist就记录了从源到所有其它顶点之间的最短路径长度。

例如,对下图中的有向图,应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下表中。

Dijkstra算法的迭代过程:



 

主题好好理解上图!

以下是具体的实现(C/C++):

  1 #include <iostream>
  2 using namespace std;
  3  
  4 const int maxnum = 100;
  5 const int maxint = 999999;
  6  
  7 // 各数组都从下标1开始
  8 int dist[maxnum];     // 表示当前点到源点的最短路径长度
  9 int prev[maxnum];     // 记录当前点的前一个结点
 10 int c[maxnum][maxnum];   // 记录图的两点间路径长度
 11 int n, line;             // 图的结点数和路径数
 12  
 13 // n -- n nodes
 14 // v -- the source node
 15 // dist[] -- the distance from the ith node to the source node
 16 // prev[] -- the previous node of the ith node
 17 // c[][] -- every two nodes' distance
 18 void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
 19 {
 20     bool s[maxnum];    // 判断是否已存入该点到S集合中
 21     for(int i=1; i<=n; ++i)
 22     {
 23         dist[i] = c[v][i];
 24         s[i] = 0;     // 初始都未用过该点
 25         if(dist[i] == maxint)
 26             prev[i] = 0;
 27         else
 28             prev[i] = v;
 29     }
 30     dist[v] = 0;
 31     s[v] = 1;
 32  
 33     // 依次将未放入S集合的结点中,取dist[]最小值的结点,放入结合S中
 34     // 一旦S包含了所有V中顶点,dist就记录了从源点到所有其他顶点之间的最短路径长度
 35          // 注意是从第二个节点开始,第一个为源点
 36     for(int i=2; i<=n; ++i)
 37     {
 38         int tmp = maxint;
 39         int u = v;
 40         // 找出当前未使用的点j的dist[j]最小值
 41         for(int j=1; j<=n; ++j)
 42             if((!s[j]) && dist[j]<tmp)
 43             {
 44                 u = j;              // u保存当前邻接点中距离最小的点的号码
 45                 tmp = dist[j];
 46             }
 47         s[u] = 1;    // 表示u点已存入S集合中
 48  
 49         // 更新dist
 50         for(int j=1; j<=n; ++j)
 51             if((!s[j]) && c[u][j]<maxint)
 52             {
 53                 int newdist = dist[u] + c[u][j];
 54                 if(newdist < dist[j])
 55                 {
 56                     dist[j] = newdist;
 57                     prev[j] = u;
 58                 }
 59             }
 60     }
 61 }
 62  
 63 // 查找从源点v到终点u的路径,并输出
 64 void searchPath(int *prev,int v, int u)
 65 {
 66     int que[maxnum];
 67     int tot = 1;
 68     que[tot] = u;
 69     tot++;
 70     int tmp = prev[u];
 71     while(tmp != v)
 72     {
 73         que[tot] = tmp;
 74         tot++;
 75         tmp = prev[tmp];
 76     }
 77     que[tot] = v;
 78     for(int i=tot; i>=1--i)
 79         if(i != 1)
 80             cout << que[i] << " -> ";
 81         else
 82             cout << que[i] << endl;
 83 }
 84  
 85 int main()
 86 {
 87     freopen("input.txt""r", stdin);
 88     // 各数组都从下标1开始
 89  
 90     // 输入结点数
 91     cin >> n;
 92     // 输入路径数
 93     cin >> line;
 94     int p, q, len;          // 输入p, q两点及其路径长度
 95  
 96     // 初始化c[][]为maxint
 97     for(int i=1; i<=n; ++i)
 98         for(int j=1; j<=n; ++j)
 99             c[i][j] = maxint;
100  
101     for(int i=1; i<=line; ++i)  
102     {
103         cin >> p >> q >> len;
104         if(len < c[p][q])       // 有重边
105         {
106             c[p][q] = len;      // p指向q
107             c[q][p] = len;      // q指向p,这样表示无向图
108         }
109     }
110  
111     for(int i=1; i<=n; ++i)
112         dist[i] = maxint;
113     for(int i=1; i<=n; ++i)
114     {
115         for(int j=1; j<=n; ++j)
116             printf("%8d", c[i][j]);
117         printf("\n");
118     }
119  
120     Dijkstra(n, 1, dist, prev, c);
121  
122     // 最短路径长度
123     cout << "源点到最后一个顶点的最短路径长度: " << dist[n] << endl;
124  
125     // 路径
126     cout << "源点到最后一个顶点的路径为: ";
127     searchPath(prev, 1, n);
128 }

输入数据:
5
7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
输出数据:
999999 10 999999 30 100
10 999999 50 999999 999999
999999 50 999999 20 10
30 999999 20 999999 60
100 999999 10 60 999999
源点到最后一个顶点的最短路径长度: 60
源点到最后一个顶点的路径为: 1 -> 4 -> 3 -> 5

 本文转自:http://www.wutianqi.com/?p=1890
其他连接:http://2728green-rock.blog.163.com/blog/static/43636790200901211848284/

posted on 2012-06-30 16:12 王海光 阅读(382) 评论(0)  编辑 收藏 引用 所属分类: 算法

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理