基于Floyd算法的道路指示牌解决方案

更新时间：2024-06-26 04:28:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

Floyd算法推荐度：
相关推荐

基于Floyd算法的道路指示牌解决方案

绪论

中国拥有13亿人口，960万平方公里的国土面积，仅次于加拿大又略大于美国；中国公路通车里程达185万公里，铁路里程达7.43万公里。在过去的20年里，我们在经济领域取得了巨大的成就，保持了强劲快速的增长态势。在中国经济增长的带动下，中国公路客运交通获得了快速发展，并以每年7％～8％的速度持续增长。与此同时，中国汽车拥有量和驾车者也都有爆发性增长；而物流运输、集装箱运输在过去的10年里增长了30％。由此可以看出，汽车产业和交通运输在中国的迅猛增长。

为了满足不断增长的交通运输，高速公路系统的建设就迫在眉睫。随着高速公路系统的不断完善，指示牌的作用十分重要。指示牌为用户指明了前往各个城市的距离。选择最短的路径，方便用户是指示牌的主要目的。

本文是基于Floyd算法，来找出设置合适的指示牌来指示用户，从而使得用户可以更加快速的到达目的地。

第一章问题模型

我们可以在每一个十字路口都设置指示牌，但这样一种方式并不是最好。为了选择哪些城市应该在指示牌上列出，我们使用如下策略：如果在指示牌前锋的十字路口上有一条路是到城市X的最短路，则城市X被标上指示牌。我们假设在没对十字路口之间只有一条最短路径。输入：

输入包括一个问题实例，描述了高速公路系统，接着是一组指示牌的位置。高速公路系统定义为一组十字路口和一组与十字路口相连的道路。第一行是是哪个正整数n、m、k：n表示十字路口的数量，m表示连接各个十字路口之间道路的数量，k表示既是城市也是十字路口的数量。接下来m行，格式是i1、i2、d，表示十字路口i1和 i2直接有一条双行道，其距离为d。接下来k行，格式是i、name，表示十字路口i是一个城市，其名字为name。在这之后的一行，有一个正整数s，表示应防止在高速公路系统上的指示牌的数量。接下来的s行，格式是i1、i2、d，表示从i1到 i2应放置一个指示牌，从i1开始的距离是d。对于所有的问题实例，名字的长短≤18个字符，5≤n≤30.所有的距离大于0，并精确到百分之一。输出：

每个指示牌的输出格式如下：

name1 d1 name2 d2 ...

namei应该左对齐，宽度为20；距离dj应四舍五入到整数。没对“name——distance”应该按四舍五入后的距离排序；相同距离的依字幕顺序输出。指示牌输出顺序应该与指示牌的输入顺序一致，每个指示牌之间有一个空行，你可以假设每个指示牌上至少列出一个城市。

第二章算法简介

Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

1.核心思路

通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。

采用的是(松弛技术)，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);

其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]} map[i,j]表示i到j的最短距离 K是穷举i,j的断点

map[n,n]初值应该为0，或者按照题目意思来做。

当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路。

2.算法描述

a) 初始化：D[u,v]=A[u,v] b) For k:=1 to n For i:=1 to n For j:=1 to n

If D[i,j]>D[i,k]+D[k,j] Then D[I,j]:=D[I,k]+D[k,j];

c) 算法结束：D即为所有点对的最短路径矩阵

3.算法过程

1.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

2.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

把图用邻接距阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=无穷大。

定义一个距阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。

把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。

比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。

4.优缺点分析

Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单

缺点：时间复杂度比较高，不适合计算大量数据。

第三章算法分析

1.样例分析

该样例有8个十字路口，17条道路，4个城市和3个指示牌。如图。

输出结果分别是三个指示牌上的城市列表。例如从路口3到路口2，在距离路口3为0.45英里处立一块指示牌，表示到Bobtown还有7英里。

2.数据结构

使用邻接矩阵存储高速公路系统图： double graph[MaxN][MaxN];

对于样例数据，数组graph的内容如图所示：数组的下表与十字路口的编号一致。

0 1 2 3 4 5 6 7 0 0.00 7.12 8.34 5.33 5.36 0.00 0.00 0.00 1 7.12 0.00 4.21 0.00 0.00 0.00 6.99 2 8.34 4.21 0.00 2.74 0.00 0.00 5.04 3 5.33 0.00 2.74 0.00 4.12 7.72 5.71 0.00 4 5.36 0.00 0.00 4.12 0.00 8.94 5 0.00 0.00 0.00 7.72 8.94 0.00 6 0.00 6.99 5.04 5.71 7 0.00 10.26 0.00 0.00 10.29 0.00 5.47 0.00 6.01 8.55 6.01 0.00 10.29 5.47 0.00 8.55 10.26 0.00 数组city表示城市： char city[MaxN][MaxN];

对于样例数据，数组city的内容如图所示：下标城市 0 Allentown 1 Bobtown 2 3 Charlestown Downville 下标是城市编号。

数组citylocation表示城市在十字路口的位置： int citylocation[MaxN]；

对于样例数据，数组citylocation的内容如图所示：下标 0 1 1 2 -1 3 -1 4 -1 5 -1 6 2 7 3 城市0 编号下标是十字路口编号，值为-1时表示该路口没有城市。

3.使用Floyd方法计算所有路口之间的最短路径

采用数组path存储最短路径： double path[MaxN][MaxN]；对于样例数据，数组path的内容如下：

注意表中阴影部分的单元格，其数值没有变化，表示这些路口之间没有最短路径。

4.计算最短路径经过的十字路口

采用数组shortpath存储最短路径经过的十字路口： int shortpath[MaxN][MaxN]; 0 1 2 3 4 5 6 7 0 0.00 7.12 8.07 5.33 5.36 1 7.12 0.00 4.21 6.95 2 8.07 4.21 0.00 2.74 3 5.33 6.95 2.74 0.00 4.12 4 5.36 5 6 7 13.05 11.04 17.05 10.26 11.05 11.72 15.84 8.55 6.01 0.00 11.07 12.46 6.99 6.86 4.12 0.00 8.94 9.83 10.46 5.04 7.72 8.94 0.00 5.47 5.71 9.83 5.47 0.00 6.01 11.07 6.86 13.05 12.46 10.46 7.72 11.04 6.99 5.04 5.71 17.05 10.26 11.05 11.72 15.84 8.55 对于样例数据，数组shortpath的内容如图所示：

0 1 2 3 4 5 6 7 0 -1 0 3 0 0 3 3 6 1 1 -1 1 2 3 6 1 1 2 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 6 3 6 6 6 3 6 -1 6 7 3 7 6 6 3 7 7 -1 当路口没有城市时，就不必计算，令其值为-1.表中的阴影单元与path表示对应的，表示没有最短路径通往其他城市。单元（i，j）（i，j=0~n-1）的值为k（k≠-1，j）时，表示从路口i到路口j有最短路径，且经过路口k。

5.计算指示牌

有了shortpath表，计算只是牌列表就容易了。如从路口i到路口k，在shortpath表中，扫描i行，其值为k时，所对应的列号j就是要列表显示的城市。列表的数据结构如下: struct sign {

int cityname，distance； }sighlist[MaxN]；

输出时要排序，采用标准函数qsort()，排序算法为函数cmp（）：首先按里程的大小升序，在里程相等的情况下，按城市名称的字幕排序。

附：程序源代码 #include #include #include #include

const int MaxN = 31; const double Zero = 0.0001; //指示牌上要显示的城市列表 struct sign {

int cityName, distance;

} signList[MaxN];

char city[MaxN][MaxN]; //城市名称 //比较函数

int cmp(const void *a1,const void *b1) {

sign *a = (struct sign*)a1; sign *b = (struct sign*)b1;

//首先按里程的大小升序

if (a->distance > b->distance) return 1;

//在里程相等的情况下，按城市名称的字幕顺序排序

}

else if (a->distance == b->distance)

return strcmp(city[a->cityName], city[b->cityName]);

else return -1;

int main() {

double path[MaxN][MaxN]; //存储最短路径 double graph[MaxN][MaxN]; //存储高速公路系统图 int shortPath[MaxN][MaxN]; //存储最短路径经过的十字路口 int cityLocation[MaxN]; //存储城市在十字路口的位置 int cases; //测试例数 scanf(\int iCase;

for (iCase = 1; iCase <= cases; iCase++) {

int i, j, k; int a, b; double d; char name[MaxN];

int n, m, cross; //路口数量，道路数量，城市数量 scanf(\

memset(graph, 0, sizeof(graph));

memset(cityLocation, 255, sizeof(cityLocation));

//构造邻接矩阵

for (i = 1; i <= m; i++) { }

scanf(\graph[a][b] = graph[b][a] = d;

//读取城市信息

for (i = 0; i < cross; i++) { }

scanf(\cityLocation[a] = i; scanf(\strcpy(city[i], name);

//使用Floyd方法计算所有路口之间的最短路径