-
Floyd
最短路径算法
2006-10-20, by leon_jlu
在图论中经常会遇到这样的问题，在一个有向图里，求出
任意两个节点之间
的最短距离。
我们在离散数学、
数据结构课上都遇到过这个问题，
在计算机网络
里介
绍网络层的时候好像也遇到过这个问题，记不请了
...
但是
书本上一律采取
的是
Dijkstra
算法，通过
Dijkstra
算法可以求出单源最短路径，然后
逐个节点利
用
Dijkstra
算法就
可以了。
不过在这里想换换口味，
采取
Robert Floyd
提出的算
法来解决这个问题。下面让
我们先把问题稍微的形式化一下：
如果有一个矩阵
D=[d(ij)]
，其中
d(ij)>0
表示
i
城市到
j
城市的距离。若
i
与
j
之间无路可通，那么
d(ij)
就是
无穷大。又有
d(ii)=0
。编写一个程序，通过
这个距离矩阵
D
，把任意两个城市之间的最短与其
行径的路径找出来。
我们可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进
< br>路线。
如何找出最短路径呢，
这里还是用到动态规划的知
识，
对于任何一个城市
而言，
i
到
j
的最短距离不外乎存在经过
i
与
j
之间的
k
和不经过
k
两种可能，所
以可以令
k=1
，
2
，
3
，
...
，
n(n
是城市的数目
)
，在检查
d(ij)
与
d(ik)+d(kj)
的值；
在此
d(ik)
与
d(kj)
分别是目前为止所知道的
i
到
k
与
k
到
j
的最短距离，因此
d(ik)+d(kj)
就是
i
到
j
经过
k
的最短距离。
所以，
若有
d(ij)>d(ik)+d(kj)
，<
/p>
就表示
从
i
出发
经过
k
再到
j
的距离要比原来的
i
到
j
距离短，自然把
i
到
j
的
d(ij)
重写
为
d(ik)+d(kj)
，每当一个
k
查完了，
d(ij)
就是目前的
i
到
j
的最短距离
。重复这
一过程，
最后当查完所有的
k
时，
d(ij)
里面存放的就是
i
到
j
之间的最短距
离了。
所以我们就可以用三个
for
循
环把问题搞定了，但是有一个问题需要注意，那就
是
for
循环的嵌套的顺序：我们可能随手就会写出这样的程序，但是仔细考虑的
话，会发现是有问题的。
<
br>短的距离时也不能再去更新了， p(ij)=i
i
<
br>i <
br>路径为 i
k->...->j 上一个城市 <
br>。 下面是具体的
<
br>路径的花费值，就是该路径上所有边的花费值总和。 及 <
br>s
到 <
br>u <
br>那么从 <
br>的最短路径可以通过将边
for(int i=0; i
for(int
j=0; j
for(int
k=0; k
问题出在我们太早的把
i-k-
j
的距离确定下来了，假设一旦找到了
i-p-j
最短
的距离后，
i
到
j
就相当处理完了，以后不会在改变了，一旦以后有使
i
到
j
的更
所以结果一定是不对的。
所以应当象下面一样来
写程序：
for(int k=0; k
for(int j=0; j
这样作的意义在于固定了
k
，
把所有
i
到
j
而经过
k
的距离找
出来，
然后象开
头所提到的那样进行比较和重写，因为
k
是在最外层的，所以会把所有的
i
到
j
都处理完后，
才会移
动到下一个
k
，
这样就不会有问题了，
看来多层循环的时候，
我们一定要当心，否则很容易就弄错了。
接下来就要看一看如何找出最短路径所行经的城市了，
这里要用到另一个矩
阵
P
，它的定义是这样的：
p(ij)
的值如果为
p
，就表示
i
到
j
的最短行经
为
i->...->p->j
，也就是说
p
是
i
到
j
的最短行径中的
j
之前的最后一个城市
。
P
矩
阵的初值为
。有了这个矩阵之后，要找最短路径就轻而易举了。对于
i
到
j
而言找出
p(ij)
，
令为
p<
/p>
，
就知道了路径
i->...->p->
j
；
再去找
p(ip)
，
如果值为
q
，
i
到
p
的最短路径为
i->...->q->p
；再去找
p(iq
)
，如果值为
r
，
到
q
的最短路径
为
i->...->r->q
；
所以一再反复，
到了某个
p(it)
的值为
i
时，
就表示
到
t
的最短
i->t
，就会的到答案了，
到
j
的最短行径为
i->t->...->q->p->j
。因为上
述
的算法是从终点到起点的顺序找出来的，所以输出的时候要把它倒过来。
但是，如何动态的回填
P
矩阵的值呢？回想一下，当
d(ij)>
d(ik)+d(kj)
时，
就要让
i
到
j
的最短路径改为走
i->...->k->...->j
这一条路，但是
d(kj)
的值是已
知的，换句话说，就是
这条路是已知的，所以
k->...-
>j
这条路上
j
的
(
即
p(kj))
也是已知的，
当然，
因为要改走
i->...->k->...->j
这一条路，
j
的上一个城市正好是
p(kj)
。所
以一旦发现
d(ij)>d(ik)+d(kj)
，就把
p(kj)
存入
p(ij)
C
代码：
#include
#include
#include
#define
MAXSIZE
20
void floyd(int [][MAXSIZE], int
[][MAXSIZE], int);
void
display_path(int [][MAXSIZE], int [][MAXSIZE],
int);
void reverse(int
[], int);
void
readin(int [][MAXSIZE], int *);
#define
MAXSUM(a, b)
(((a) != INT_MAX && (b)
!= INT_MAX) ?
((a) + (b)) : INT_MAX)
void floyd(int
dist[][MAXSIZE], int path[][MAXSIZE], int n)
{
int i, j,
k;
for (i = 0; i < n; i++)
for (j =
0; j < n; j++)
path
[j] = i;
for (k = 0;
k < n; k++)
for (i = 0; i < n;
i++)
for (j = 0; j < n; j++)
if
(dist[j] > MAXSUM(dist[k], dist[k][j]))
{
path[j] = path[k][j];
dist[j] = MAXSUM(dist[k], dist[k][j]);
}
}
void
display_path(int dist[][MAXSIZE], int
path[][MAXSIZE], int n)
{
int *chain;
int count;
int i, j,
k;
printf(
Dist
ath
printf(
chain = (int
*) malloc(sizeof(int)*n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
if (i !=
j)
{
printf(
if (dist[j] == INT_MAX)
printf(
else
{
printf(
count = 0;
k = j;
do
{
k = chain[count++] =
path[k];
} while (i != k);
reverse(chain, count);
printf(
for (k = 1;
k < count; k++)
printf(
printf(
}
}
}
free(chain);
}
#define SWAP(a, b) { temp = a; a = b; b = temp; }
void
reverse(int x[], int n)
{
int i, j, temp;
for (i = 0, j = n-1; i < j; i++, j--)
SWAP(x, x[j]);
}
void readin(int dist[][MAXSIZE], int
*number)
{
int origin,
dest, length, n;
int i, j;
char
line[100];
gets(line);
sscanf(line,
*number = n;
for (i = 0; i < n; i++)
{
for (j = 0; j < n;
j++)
dist[j] = INT_MAX;
dist =
0;
}
gets(line);
sscanf(line,
while (origin != 0 && dest
!= 0 && length != 0)
{
dist[origin-1][dest-1] = length;
gets(line);
sscanf(line,
}
}
测试程序如下所示：
int main(void)
{
int
dist[MAXSIZE][MAXSIZE];
int
path[MAXSIZE][MAXSIZE];
int n;
printf(
printf(
readin(dist,
&n);
floyd(dist, path, n);
display_path(dist, path, n);
getchar();
}
其中
readin
函数规定了输入的格式，
第一列是指出有多少个
城市；
第二列以
后每行三个数；
第一个
和第二个是一条路径的起点和终点，
第三个数是路径的长
度，最
后以三个
0
作为输入结束条件。下面是一个输入的例子：
Input the path
information:
--------------------------------------
4
1
2
5
2
1
50
2
3
15
2
4
5
3
1
30
3
4
15
4
1
15
4
3
5
0
0
0
对应的输出结果为：
Origin->Dest
Dist
Path
----------------------------------------------
1->2
5
1->2
1->3
15
1->2->4->3
1->4
10
1->2->4
2->1
20
2->4->1
2->3
10
2->4->3
2->4
5
2->4
3->1
30
3->1
3->2
35
3->1->2
3->4
15
3->4
4->1
15
4->1
4->2
20
4->1->2
4->3
5
4->3
Dijkstra
算法是由荷兰计算
机科学家艾兹格
?
迪科斯彻发现的。
算
法解决的是有向
图中最短路径问题。
举例来说，
如果图中的顶点表示城市，
而边上的权重表示著城市间开车行经的距
离。
Dijkstra
算法可以用来找到两个城市之间的最短路径。
Dijkstra
算法的
输入包含了一个有权重的有向图
G
，
以
及
G
中的一个来源顶点
S
。
我们以
V
表示
G
中所有顶点的集合。
每一个图中的边，都是两个顶点所形成的
有序元素对。
(u,v)
表示从顶点
u
到
v
有路径相连。
我们以
E
所有边的集合，而
边
的权重则由权重函数
w: E
→
[0, ∞]
定义。
因此，
w(u,v)
就是从顶点
u
到顶
点
v
的非负花费值
(cost)
。
边的花费可以想像成两个顶点之间的距离。
任两点间
已
知有
V
中有顶点
s
t
，
Dijkstra
算法可以找到
s
到
t<
/p>
的最低花费路径
(i.e.
最短路径
)
。
这个算法也可以
在一个图中，找到从一个顶点
到任何其他顶点的最短路径。
算法描述
这个算法是通过为每个顶点
v
保留目前为止所找到的从
s
到
v
的最短路径来工
作
的。初始时，源点
s
的路径长度值被
赋为
0
（
d[s]=0
），
同时把所有其他顶点
的
路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于
V
中所有顶点
v
除
s
外
d[v]= ∞
）。当算法结束时，
d[v]
中储存的便是从
s
v
的
最短路径，或者如果路径不
存在的话是无穷大。
Dijstra
算法的基础操作是边的
拓展：
如果存在一条从
到
v
的边，
s
到
u
(u,v)
添加到尾部来拓展一
条从
s
到
v
的
路径。这条路径的长度是
d+w(u,v)
。如果这
个值比目前已知的
d[v]
的值要小，
我们可以用新值来替代当前
d[v]
中的值。
拓展
边的操作一直执行到所有的
d[v]<
/p>
都代表从
s
到
v
最短路径的花费。
这个算法经过
组织因
而当
d
达到它最终的值的时候没条边
(
u,v)
都只被拓展一次。
算法维护
两个顶点集
S
和
Q
。集合
S
保留了我们已知的所有
d
[v]
的值已经是最
短路径的值顶点，而集合
< br>Q
则保留其他所有顶点。集合
S
初始状态为空，而后
每一步都有一个顶点从
Q
< br>移动到
S
。这个被选择的顶点是
Q
中拥有最小的
d
值
< br>的顶点。
当一个顶点
u
从
Q
中转移到了
S
中，
算法对每条外接边
(u,v)
进行拓展
。
在下面的算法中
,u:=Extract_Min(Q)
在在顶点集
Q
中搜索有最小的
d
值的顶点
u
。
这个顶点被从集合
Q
中删除并返回给用户。
1
function Dijkstra(G, w, s)
2
for each vertex v in V[G]
//
初始化
3
d[v] :=
infinity
4
previous[v] := undefined
5
d[s] := 0
6
S := empty set
7
Q := set of all vertices
8
while Q is not an
empty set
//
Dijstra
算法主体
9
u :=
Extract_Min(Q)
10
S := S union {u}
11
for each edge (u,v) outgoing from u
12
if d[v] > d + w(u,v)
//
拓展边
(u,v)
13
d[v] := d
+ w(u,v)
14
previous[v] := u
如果我们只对在
s
和
t
之间寻找一条最短路径的话，
我们可以在第
9
行添加条件
如果满足
u=t
的话终止程序。
<
/p>
现在我们可以通过迭代来回溯出
s
到
t
的最短路径
1
S := empty sequence
2 u :=
t
3 while defined u
4
insert u to the beginning
of S
5
u := previous
现在序列
S
就是从
s
到
t
的最短路径的顶点集
.
本人自己
写的蚁群算法。完全能
够实现功能，就是收敛速度感觉有点慢。
%
function
[R_bes
t,L_best,L_ave,Shortest_Route,Shortest_Length]=ACO
(C,D,s,e,NC_ma
x,m,Alpha,Beta,Rho,Q)
%
function
[Short
est_Route,Shortest_Length]=ACOR(C,D,s,e,NC_max,m,A
lpha,Beta,Rho,
Q)
%%=========
===================================
====
=========================
%% ACO.m
%% Ant Colony Optimization Algorithm
for Road Select Problem
%%
LiLixin,ShenYang Insitute of Aeronautical
engineering ,ShenYang,China
%%
Email:myassist@
%% All rights reserved
%%-------------------------------------
------------------------------------
%%
主要符号说明
%% C n
个城市的坐标，
n×
2
的矩阵
%% D
道路连通加权矩阵
%% s
起点
%% e
终点
%% NC_max
最大迭代次数
%% m
蚂蚁个数
%% Alpha
表征信息素重要程度的参数
%%
Beta
表征启发式因子重要程度的参数
%% Rho
信息素蒸发系数
%% Q
信息素增加强度系数
%% R_best
各代最佳路线
%% L_best
各代最佳路线的长度
%%=====
=======================================
=============================
%
clc
clear
%
设置初始参数如下：
m=10;Alpha=1;Beta=5;Rho=0.1;NC_max=100;Q=100 ;
%
设定起始点
s=1;e=50;
%
31
城市坐标为：
C=[601.6
971.7
988.8
482.6
54.4
549.6
95.4
868
529.1
429.5
982
350.5
654.3
23.2
738.1
372
538.9
593.7
560.1
850.3
229.2
805.9
411.2
710
83.2
706.2
937.4
800.5
11.9
994.4
694.1
809.1
795.4
758.8
338.9
148.1
955.8
643.8
345.7
726.2
550.3
349.6
183.7
935.1
640
544
854.6
842.4
199.3
547.9
434.1
921.4
405.5
624.2
272.3
998.1
772
24.4
385.2
327.4
320.3
410.4
890
90
810
580
180
80
185
300
950
200
850
258.6
50
450
150
402
345
900
450
800
621
700
564.3
180
80.5
280
750
950
450
500
300
50
900
530
300
520
152
189.6
];
D=[0
0
0
0
0
0
0
0
0
76.92
0
0
0
0
0
230.95
0
0
0
0
0
0
0
0
0
76.8
94
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
157.34
0
0
0
0
0
0
0
0
0
0
140.78
0
325.12
0
0
0
0
0
0
0
0
0
0
155.71
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
76.913
0
0
0
0
0
0
0
0
0
0
0
0
0
0
74.247
0
0
0
0
0
0
0
0
0
0
0
55.603
0
0
0
0
0
0
0
0
0
0
0
0
76.921
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
147.8
0
76.551
0
76.908
0
0
0
0
0
0
79.548
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
84.189
0
0
0
0
0
0
0
0
166.74
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
76.915
0
0
0
0
0
140.78
0
0
0
0
0
211.43
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
76.91
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
205.65
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
76.91
0
0
0
0
0
0
0
0
0
0
0
0
0
76.901
0
0
0
156.87
0
0
0
0
325.12
0
0
0
211.43
205.65
0
0
0
0
0
0
0
0
0
0
0
0
0
79.979
0
258.19
0
0
0
0
0
0
0
0
0
0
0
0
0
73.841
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
76.898
0
0
0
0
0
0
0
0
0
0
79.382
0
0
0
75.438
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
76.92
0
0
0
0
0
0
0
0
0
0
0
0
0
0
80.01
0
0
0
0
0
0
0
0
0
79.064
0
0
0
0
0
0
0
0
0
0
0
0
0
0
76.919
0
0
0
0
0
0
0
0
0
0
0
0
147.8
0
0
0
0
0
0
0
0
147.14
0
0
0
0
0
0
163.89
0
60.464
0
0
0
0
0
151.26
0
0
0
0
0
0