最短路径算法—Dijkstra(迪杰斯特拉)算法分析与实现(C/C++)

Dijkstra算法

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

输入数据:
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

最后给出两道题目练手,都是直接套用模版就OK的:
1.HDOJ 1874 畅通工程续
http://www.wutianqi.com/?p=1894

2.HDOJ 2544 最短路
http://www.wutianqi.com/?p=1892

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《最短路径算法—Dijkstra(迪杰斯特拉)算法分析与实现(C/C++)》有85个想法

      1. 您是指在更新dist函数当中嘛
        我想说的是 我该如何存储这些具有相同路径的这些顶点 因为我需要用到这些顶点 需要把所有的可能都输出来 不是只求最短路径 输出一条
        谢谢!

  1. 大哥,我用VS2010打开,怎么运行不了呢,你看看。平常用VSC++6.0不太会VS2010
    1>c:\users\administrator\desktop\test\a\a\a.cpp(1): warning C4627: “#include < iostream > ”: 在查找预编译头使用时跳过
    1> 将指令添加到“StdAfx.h”或重新生成预编译头
    1>c:\users\administrator\desktop\test\a\a\a.cpp(128): fatal error C1010: 在查找预编译头时遇到意外的文件结尾。是否忘记了向源中添加“#include “StdAfx.h””?
    1>
    1>生成失败。

  2. 大哥,我用VS2010大打开,怎么运行不了呢,你看看。平常用VSC++不太会VS2010
    1>c:\users\administrator\desktop\test\a\a\a.cpp(1): warning C4627: “#include ”: 在查找预编译头使用时跳过
    1> 将指令添加到“StdAfx.h”或重新生成预编译头
    1>c:\users\administrator\desktop\test\a\a\a.cpp(129): fatal error C1010: 在查找预编译头时遇到意外的文件结尾。是否忘记了向源中添加“#include “StdAfx.h””?
    1>
    1>生成失败。

  3. 网上搜文章 看到您的文章 想请教一个问题是:
    关于Dijkstra算法的问题 你在处理最短路径问题上是考虑的无向图的?
    c[p][q] = len;
    c[q][p] = len;
    赋值的结果 是邻接矩阵是个对称矩阵?
    有向图是正确的嘛

  4. 我想问问,那个freopen(“input.txt”, “r”, stdin);
    是读取TXT数据,那下面为什么还要输入数据呢,我想问问TXT里装的是什么数据。

  5. 这个是执行的时候报的错误啊

    > Dijkstra.cpp
    1>i:\c++程序\dijkstra\dijkstra\dijkstra.cpp(120): error C2872: “prev”: 不明确的符号
    1> 可能是“i:\c++程序\dijkstra\dijkstra\dijkstra.cpp(9) : int prev[100]”
    1> 或 “c:\program files\microsoft visual studio 10.0\vc\include\xutility(963) : _InIt std::prev(_InIt,iterator_traits::difference_type)”
    1>i:\c++程序\dijkstra\dijkstra\dijkstra.cpp(127): error C2872: “prev”: 不明确的符号
    1> 可能是“i:\c++程序\dijkstra\dijkstra\dijkstra.cpp(9) : int prev[100]”
    1> 或 “c:\program files\microsoft visual studio 10.0\vc\include\xutility(963) : _InIt std::prev(_InIt,iterator_traits::difference_type)”
    1>

    1. 对啊,你把这完整错误贴出来不是一下子就好说了嘛。。。
      我定义的prev数组和VS2010的std::prev()函数同名了,你把prev数组名改一下就可以了。

        1. 我白天不用Q的
          你把截图贴在:http://imgur.com/,然后告诉我图片链接
          并且你要把你那边的一些问题给缩小范围,你给的提示范围太广了。不同编译器对代码的优化或报警级别设置都不一样

发表评论

电子邮件地址不会被公开。 必填项已用*标注