图论公交选路问题中的应用

图 论

题 目 公交选路在图论中的应用

姓 名 李 丽

学 号 S130101082

专 业 信息与通信工程

老 师 蒲 兴 成

得 分

2013年 12 月 19

日 公交选路在图论中的应用

摘要

在日常生活中，人们出行时无可避免的会乘坐公交汽车。那么，什么样的路线才是使人们到达目的地的最短路线呢？这是许多人关系的问题。如果把这个问题运用于图论中，就是寻找最短路劲问题。在图论中最短路径有着非常广泛的应用，

而由于应用的方法不同也形成了多种求最短路径的方法。最常见的寻求最短路的方法有迪克斯屈拉算法（Dijkstra），弗洛伊德（Floyd）算法。本文就是采用Floyd算法来寻求两点间的最短路问题。

本文大致分为五个部分。第一部分介绍图论的背景；第二部分介绍图论的基本概念；第三部分介绍Floyd算法的基本思想；第四部分介绍公交选路问题在图论中的实际应用；第五部分总结；第六部分列出该论文所用到的参考文献；第七部分附录。

关键词：公交选路 最短路 图论 Floyd 一、图论的背景

1736年是图论的历史元年。这一年，图论之父欧拉解决了哥斯尼堡城的七桥问题，发表了图论的首篇论文。美丽的哥尼斯堡始建于1308年，是东普鲁氏王朝的都市，城内的一条河的两条支流绕过一个岛，有七座桥横跨这两支流。脚下的七座桥触发了人们的灵感，人们有一项消遣活动，就是试图将河上的每座桥恰好走过一遍并回到原出发点，然而吸引了人们无数次的尝试却没人成功。问题看起来不复杂，但谁也解决不了，说不出其所以然来。直到1736年，欧拉解决了这一问题。他将这个问题转化为图论问题，即把每一块陆地用一个点来代替，将每一座桥用连接相应两个点的一条线来代替，从而得到一个点线图。欧拉只用了一步就证明了哥尼斯堡七桥问题没有解，并且推广了这个问题，给出了任意一种河桥图能否全部不重复、不遗漏走一次的判定法则：如果通过奇数座桥连接的地方不止两个，满足要求的路线不存在；如果只有两个地方通过奇数座桥连接，则可从其中任一地方出发找到所要求的路线；如果没有一个地方通过奇数座桥连接，则从任一地出发，所求路线都能实现。他还说明怎样快速找到所要的路线，并为此设计了一个15座桥的问题。欧拉的论文在圣彼得堡科学院作了报告，成为图论历史上第一篇重要文献[2]。这项工作使欧拉成为图论（及拓扑学）的创始人。

1750年，欧拉和他的一个朋友哥德巴赫通信时说发现了多面体的一个公式：设多面体的顶点数为Nv，棱数为Ne，面数为Nf，则有Nv-Ne+Nf=2[1]。这类问题成为19世纪后半叶拓扑学研究的主要问题。欧拉多面体公式表述了几何图形的

一个基本组合性质，其目的是利用这一关系将多面体进行分类。图论的发展从19世纪中叶开始，图论进入第二个发展阶段。这一时期图论问题大量出现，诸如关于地图染色的四色问题、由“周游世界”游戏发展起来的哈密顿问题等。进入20世纪，图论仍然得以继续快速发展，科学家们通过计算机技术对四色猜想进行了证明等。

二、图论的基本概念

1、图的定义

有序三元组G = < V(G)，E(G)，?(G) >称为一个图[1]，其中：

（1）V(G)={v1，v2，?，vn}是有穷非空集，称为顶点集，其元素叫做图的顶点

（2）E(G)={e1，e2，?，en}称为边集，其元素叫做图的边；

（3）?(G)；E→V?V是从边集E到顶点集V的有序或者无序对集合的影射， 称为关联函数。

2、图的分类

在图G中，与V中的有序偶（vi，vj）对应的边e称为图的有向边（或弧），而与V中顶点的无序偶对应的边e称为图形的无向边，每一条边都是无向边的图，叫做无向图，记为G = （V，E）；每一条边都是有向边的图叫做有向图，记为D =（V，E）；既有无向边又有有向边的图叫做混合图。

3、加权图

如果图G中任意一条边（vi ，vj）上都附有一个数Wij，则称这样的图G为赋权图，Wij称为边（vi，vj）上的权（weight）。

4、最短路径问题

最短路径问题（shortest path problem）是图论中的一个基本问题。在赋权图（weighted graph）中，每条边都有一个数值——权（weight，代表其长度、成本、时间等），找出两节点之间总权和最小的路径就是最短路径问题。最短路径算法包括指定顶点对之间的最短路径算法和所有顶点间的最短路径算法。在图论中最典型的两种求最短路径算法分别是Dijkstra算法和Floyd算法，其中Dijkstra算法适用于前者，而Floyd算法适用于后者。另外还有很多方法可以应用到计算最短路径，比如：直观判断、遗传算法 。

三、Floyd算法

1、Floyd算法背景

Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一，1978年图灵奖获得者，斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。与Dijkstra算法相比，它是求任意两点间的最短距离。Floyd算法的时间复杂度为O(n4)，相对来说，比较容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。但是，时间复杂度比较高，不适合计算大量数据[3]。

2、Floyd算法的基本思想：

可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个地点而言，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)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。

3、Floyd算法的构造原理

对一个有n个顶点的图G，将顶点用n个整数（从1到n）进行编号。把G的带权邻接矩阵W作为距离的初值，即D(0)=(dij(0))n x m=W。

第一步构造D(1)=(dij(1))n x m ，其中dij(1)=min{ dij(0)，di1(0)+d1j(0) }是从vi到vj

的只允许以v1作为中间点的路径中最短路长度。

第二步构造D(2)=(dij(2))n x m ，其中dij(2)=min{ dij(1)，di2(1)+d2j(1) }是从vi到vj

的只允许以v1 、v2作为中间点的路径中最短路长度。

第n步构造D(n)=(dij(n))n x m ，其中dij(n)=min{ dij(n)，din(n)+dnj(n) }是从vi到vj

的只允许以v1、v2、?、vn作为中间点的路径中最短路长度，即是从vi到vj中间可插入任何顶点的路径中最短路的长度，因此D(n)即是距离矩阵[1]。

四、公交选路的实例