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. /***************************************
2. * About: 有向图的 Dijkstra 算法实现
3. * Author: Tanky Woo
4. * Blog: www.WuTianQi.com
5. ***************************************/
6.
7. #include <iostream>
8. using namespace std;
9.
10. const int maxnum = 100;
11. const int maxint = 999999;
12.
13.
14. void Dijkstra(int n, int v, int *dist, int *prev, int
c[maxnum][maxnum])
15. {
评论4