定义
Dijkstra算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。
原理
1.首先，引入一个辅助数组(vector)D，它的每个元素表示当前所找到的从起始点（即源点）到其它每个顶点的长度。
例如，表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。
2.D的初始状态为：若从到有弧（即从到存在连接边），则为弧上的权值（即为从到的边的权值）；否则置为∞。
显然，长度为的路径就是从出发到顶点的长度最短的一条路径，此路径为。
3.那么，下一条长度次短的是哪一条呢？也就是找到从源点到下一个顶点的最短路径长度所对应的顶点，且这条最短路径长度仅次于从源点到顶点的最短路径长度。
假设该次短路径的终点是，则可想而知，这条路径要么是，或者是。它的长度或者是从到的弧上的权值，或者是加上从到的弧上的权值。
4.一般情况下，假设S为已求得的从源点出发的最短路径长度的顶点的集合，则可证明：下一条次最短路径（设其终点为）要么是弧，或者是从源点出发的中间只经过S中的顶点而最后到达顶点的路径。
因此，下一条长度次短的的最短路径长度必是，其中要么是弧上的权值，要么是和弧上的权值之和。
算法描述如下：
1）令arcs表示弧上的权值。若弧不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到的从出发的的终点的集合，初始状态为空集。那么，从出发到图上其余各顶点可能达到的长度的初值为；
2）选择，使得；
3）修改从出发的到集合V-S中任一顶点的最短路径长度。
问题描述
在有向图G=(V,E)中，假设每条边E[i]的长度为w[i]，找到由顶点V0到其余各点的最短值。
算法思想
按路径长度递增次序产生算法：
把顶点集合V分成两组：
（1）S：已求出的顶点的集合（初始时只含有源点V0）
（2）V-S=T：尚未确定的顶点集合
将T中顶点按递增的次序加入到S中，保证：
（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度
（2）每个顶点对应一个距离值
S中顶点：从V0到此顶点的长度
T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度
依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。
（反证法可证）
求最短路径步骤
算法步骤如下：
G={V,E}
1.初始时令S={V0},T=V-S={其余顶点}，T中顶点对应的距离值
若存在，d(V0,Vi)为弧上的权值
若不存在，d(V0,Vi)为∞
2.从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中
3.对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止。
算法实现
pascal语言
下面是该算法的Pascal程序
1
type
|
2
bool=array[1..10]ofboolean;
|
3
arr=array[0..10]ofinteger;
|
4
var
|
5
a:array[1..10,1..10]ofinteger;//存储图的邻接数组，无边为10000
|
6
c,d,e:arr;//c为最短路径数值,d为各点前趋,
|
7
t:bool;//e：路径，t为辅助数组
|
8
i,j,n,m:integer;
|
9
inf,outf:text;
|
10
procedure init;//不同题目邻接数组建立方式不一样
|
11
begin
|
12
assign(inf,inputfile);
|
13
assign(outf,outputfile);
|
14
reset(inf);
|
15
rewrite(outf);
|
16
read(inf,n);
|
17
for i:= 1 to n do
|
18
begin
|
19
for j := 1 to n do
|
20
begin
|
21
read(inf,a[i,j]);
|
22
if a[i,j]=0 then
|
23
a[i,j]:=10000;
|
24
end;
|
25
end;
|
26
end;
|
27
procedure dijkstra(qi:integer;t:bool;varc{,d}:arr);
|
28
//qi起点,{}中为求路径部分,不需求路径时可以不要
|
29
var
|
30
i,j,k,min:integer;
|
31
begin
|
32
t[qi]:=true;
|
33
//t数组一般在调用前初始,除起点外所有节点都化成false,也可将部分点初始化成true以回避这些点
|
34
for i:= 1 to n do
|
35
d[i] := qi;
|
36
d[qi]:=0;
|
37
for i:=1 to n do
|
38
c[i]:=a[qi,i];
|
39
for i:= 1 to n-1 do
|
40
begin
|
41
min:=maxint;//改为最大值
|
42
for j:=1 to n do
|
43
if(c[j]
|
44
begin
|
45
k:=j;
|
46
min:=c[j];
|
47
end;
|
48
t[k]:=true;
|
49
for j:=1 to n do
|
50
if(c[k]+a[k,j]
|
51
begin
|
52
c[j]:=c[k]+a[k,j];
|
53
d[j]:=k;
|
54
end;
|
55
end;
|
56
end;
|
57
|
58
procedure make(zh:integer;d:arr;vare:arr);//生成路径,e[0]保存路径
|
59
var
|
60
i,j,k:integer;//上的节点个数
|
61
begin
|
62
i:=0;
|
63
while d[zh]<>0 do
|
64
begin
|
65
inc(i);
|
66
e[i]:=zh;
|
67
zh:=d[zh];
|
68
end;
|
69
inc(i);
|
70
e[i]:=qi;
|
71
e[0]:=i;
|
72
end;
|
主程序调用：求长度：初始化t，然后dijkstra(qi,t,c,d)
求路径：make(m,d,e)，m是终点
C语言
下面是该算法的C语言实现
1
#include
|
2
#include
|
3
#define max1 10000000 //原词条这里的值太大，导致溢出，后面比较大小时会出错
|
4
int a[1000][1000];
|
5
int d[1000];//d表示源节点到该节点的最小距离
|
6
int p[1000];//p标记访问过的节点
|
7
int i, j, k;
|
8
int m;//m代表边数
|
9
int n;//n代表点数
|
10
int main()
|
11
{
|
12
scanf("%d%d",&n,&m);
|
13
int min1;
|
14
int x,y,z;
|
15
for(i=1;i<=m;i++)
|
16
{
|
17
scanf("%d%d%d",&x,&y,&z);
|
18
a[x][y]=z;
|
19
a[y][x]=z;
|
20
}
|
21
for( i=1; i<=n; i++)
|
22
d[i]=max1;
|
23
d[1]=0;
|
24
for(i=1;i<=n;i++)
|
25
{
|
26
min1 = max1;
|
27
//下面这个for循环的功能类似冒泡排序，目的是找到未访问节点中d[j]值最小的那个节点，
|
28
//作为下一个访问节点，用k标记
|
29
for(j=1;j<=n;j++)
|
30
if(!p[j]&&d[j]
|
31
{
|
32
min1=d[j];
|
33
k=j;
|
34
}
|
35
//p[k]=d[k]; // 这是原来的代码，用下一 条代码替代。初始时，执行到这里k=1，而d[1]=0
|
36
//从而p[1]等于0，这样的话，上面的循环在之后的每次执行之后，k还是等于1。
|
37
p[k] = 1; //置1表示第k个节点已经访问过了
|
38
for(j=1;j<=n;j++)
|
39
if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
|
40
d[j]=d[k]+a[k][j];
|
41
}
|
42
//最终输出从源节点到其他每个节点的最小距离
|
43
for(i=1;i
|
44
printf("%d->",d[i]);
|
45
printf("%dn",d[n]);
|
46
return 0;
|
47
}
|
大学经典教材<<数据结构>>(C语言版 严蔚敏 吴为民 编著)中该算法的实现
1
/*
|
2
测试数据 教科书 P189 G6 的邻接矩阵 其中 数字 1000000 代表无穷大
|
3
6
|
4
1000000 1000000 10 100000 30 100
|
5
1000000 1000000 5 1000000 1000000 1000000
|
6
1000000 1000000 1000000 50 1000000 1000000
|
7
1000000 1000000 1000000 1000000 1000000 10
|
8
1000000 1000000 1000000 20 1000000 60
|
9
1000000 1000000 1000000 1000000 1000000 1000000
|
10
结果：
|
11
D[0] D[1] D[2] D[3] D[4] D[5]
|
12
0 1000000 10 50 30 60
|
13
*/
|
14
#include
|
15
#include
|
16
#define MAX 1000000
|
17
using namespace std;
|
18
int arcs[10][10];//邻接矩阵
|
19
int D[10];//保存最短路径长度
|
20
int p[10][10];//路径
|
21
int final[10];//若final[i] = 1则说明 顶点vi已在集合S中
|
22
int n = 0;//顶点个数
|
23
int v0 = 0;//源点
|
24
int v,w;
|
25
void ShortestPath_DIJ()
|
26
{
|
27
for (v = 0; v < n; v++) //循环 初始化
|
28
{
|
29
final[v] = 0; D[v] = arcs[v0][v];
|
30
for (w = 0; w < n; w++) p[v][w] = 0;//设空路径
|
31
if (D[v] < MAX) {p[v][v0] = 1; p[v][v] = 1;}
|
32
}
|
33
D[v0] = 0; final[v0]=1; //初始化 v0顶点属于集合S
|
34
//开始主循环 每次求得v0到某个顶点v的最短路径 并加v到集合S中
|
35
for (int i = 1; i < n; i++)
|
36
{
|
37
int min = MAX;
|
38
for (w = 0; w < n; w++)
|
39
{
|
40
//我认为的核心过程--选点
|
41
if (!final[w]) //如果w顶点在V-S中
|
42
{
|
43
//这个过程最终选出的点 应该是选出当前V-S中与S有关联边
|
44
//且权值最小的顶点 书上描述为 当前离V0最近的点
|
45
if (D[w] < min) {v = w; min = D[w];}
|
46
}
|
47
}
|
48
final[v] = 1; //选出该点后加入到合集S中
|
49
for (w = 0; w < n; w++)//更新当前最短路径和距离
|
50
{
|
51
/*在此循环中 v为当前刚选入集合S中的点
|
52
则以点V为中间点 考察 d0v+dvw 是否小于 D[w] 如果小于 则更新
|
53
比如加进点 3 则若要考察 D[5] 是否要更新 就 判断 d(v0-v3) + d(v3-v5) 的和是否小于D[5]
|
54
*/
|
55
if (!final[w] && (min+arcs[v][w]
|
56
{
|
57
D[w] = min + arcs[v][w];
|
58
// p[w] = p[v];
|
59
p[w][w] = 1; //p[w] = p[v] + [w]
|
60
}
|
61
}
|
62
}
|
63
}
|
64
|
65
|
66
int main()
|
67
{
|
68
cin >> n;
|
69
for (int i = 0; i < n; i++)
|
70
{
|
71
for (int j = 0; j < n; j++)
|
72
{
|
73
cin >> arcs[i][j];
|
74
}
|
75
}
|
76
ShortestPath_DIJ();
|
77
for (int i = 0; i < n; i++) printf("D[%d] = %dn",i,D[i]);
|
78
return 0;
|
79
}
|
堆优化
思考
该算法复杂度为n^2,我们可以发现，如果边数远小于n^2,对此可以考虑用堆这种数据结构进行优化，取出最短路径的复杂度降为O(1)；每次调整的复杂度降为O（elogn）；e为该点的边数，所以复杂度降为O((m+n)logn)。
实现
1.将源点加入堆，并调整堆。
2.选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。
3.处理与u相邻的，未被访问过的，满足三角不等式的顶点
1):若该点在堆里，更新距离，并调整该元素在堆中的位置。
2):若该点不在堆里，加入堆，更新堆。
4.若取到的u为终点，结束算法；否则重复步骤2、3。
Java代码
1
//假设起点为src, 终点为dst, 图以二维矩阵的形式存储，若graph[i][j] == 0, 代表i,j不相连
|
2
//visit[i] == 0,代表未访问,visit[0] == -1代表已访问
|
3
public int Dijkstra(int src, int dst, int[][] graph,int[] visit){
|
4
//节点个数
|
5
int n = graph.length;
|
6
PriorityQueue pq = new PriorityQueue<>(new Node());
|
7
//将起点加入pq
|
8
pq.add(new Node(src, 0));
|
9
while (!pq.isEmpty()){
|
10
Node t = pq.poll();
|
11
//当前节点是终点，即可返回最短路径
|
12
if(t.node == dst)
|
13
return t.cost;
|
14
//t节点表示还未访问
|
15
if (visit[t.node]==0){
|
16
//将节点设置为已访问
|
17
visit[t.node] = -1;
|
18
//将当前节点相连且未访问的节点遍历
|
19
for (int i = 0; i < n; i++) {
|
20
if (graph[t.node][i]!=0 && visit[i]==0) {
|
21
pq.add(new Node(i, t.cost + graph[t.node][i]));
|
22
}
|
23
}
|
24
}
|
25
}
|
26
return -1;
|
27
}
|
28
//定义一个存储节点和离起点相应距离的数据结构
|
29
class Node implements Comparator {
|
30
public int node;
|
31
public int cost;
|
32
|
33
public Node(){}
|
34
|
35
public Node(int node, int cost){
|
36
this.node = node;
|
37
this.cost = cost;
|
38
}
|
39
@Override
|
40
public int compare(Node node1, Node node2){
|
41
return node1.cost-node2.cost;
|
42
}
|
43
}
|
相关词条
相关搜索
其它词条
