- 1 -
基于 Dijkstra算法的铁路客运中转径路优化
余震江，王成良
重庆大学软件学院，重庆（400044）
摘 要：铁路客运中转径路优化，是基于铁路运输网拓扑结构的最优路径算法问题。因为具
有实际的应用背景，最优路径算法考虑的因素和限制条件比经典最短路径算法复杂得多，其
核心思想还是源于经典最短路径算法。本文在经典 Dijkstra 算法的基础上, 对算法和数据结
构进行了改进,并结合应用领域采取了对路网按节点层次编码、将业务逻辑融入搜索过程中
等优化方法，实现了算法的高效性和搜索路径的有效性。
关键词：最短路径；Dijkstra算法；铁路网；径路计算
0. 引言
随着经济社会不断发展和铁路运输能力的提高，铁路成为旅客出行特别是中长途旅客出
行的重要交通方式。选择铁路出行的旅客不断增加，由于不可能在任意城市的车站间都开行
直达列车，因此针对旅客出行要求提供合理的乘车方案（路径、车次、中转车站、中转次数
等）成为旅客十分关心的问题。
最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的研究热点。国内外大
量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法
的有效结合使得新的最短路径算法不断涌现[1]。最短路径问题是资源分配、路线设计及分析
等优化问题的基础,其算法是交通网络分析的核心算法之一。
在经典Dijkstra 算法中，节点无序地存储在无序表中，每次搜索与当前检查点相邻的节
点时，需要遍历所有的节点，成为算法的瓶颈。本文结合路网结构、列车等级、经由、停靠
站等业务信息，从算法运行结构和数据存储结构两方面对Dijkstra算法进行优化：一是针对
实际网络特征优化运行结构, 采用堆排序数据结构设计算法，在统一时间复杂度的基础上尽
可能地提高算法的运行效率；二是采用拓扑层次编码路径视图，减少最优路线分析过程中搜
索节点的数量，从而尽快到达目标点；三是采取节点—车次邻接表结构来描述存储铁路网和
车次信息，使搜索的结果是基于车次的而不仅是基于线路的，具有适用性。
1. 最短路算法思想和优化途径分析
最短路算法简述
最短路径算法按照路径搜索实现技术可分为组合技术和代数方法两种。组合技术主要
是指标号算法（Labeling Algorithms）,也是大多数最短路算法的核心部分。标号算法又分为
标号设定法（Labeling Setting Algorithms,简称LS算法）和标号改正法（Labeling Correcting
Algorithms，简称LC算法）。LS算法又称最短优先算法，最早由荷兰数学家Dijkstra于1959
年提出。Dijkstra算法的广泛应用，使其成为标号设定法的代名词[1]。LC算法又称列表优先
算法。LS 算法在优先级队列处理的每一步, 都能得到一条由源点到其余节点的最短路径,由
此当仅需1:1 最短路径时, 当终点跳出优先级队列时即可结束。但LS算法不能处理含负权边
的网络。而LC算法处理节点时,可能需要多次进出优先级队列, 因此源点到终点的1:1最短路
径需到算法结束时才能得到。LC算法可处理含负权边的网络。基于各种运行结构的Dijkstra
算法仍是交通网络最短路径算法的首选。
- 2 -
经典 Dijkstra 算法的主要思想
对图G(V,E),设置两个顶点的集合S和T=V-S ,集合S中存放已找到最短路径的结点,集合
T存放当前还未找到的最短路径的长度最短的结点。Dijkstra算法的输出结果是以源点V 0为
根的生成树。生成树迭代构建，当迭代过程结束，就形成最短路径树。对每个结点V i的标
号有三种：距离标号d (i)；父节点标号p(i);结点状态标号s(i)。d (i)表示从V 0到其他结点V i
的路径长度初值，w(i,j)表示弧（V i, V j）的权值。Dijkstra 算法将网络结点分为未标号结
点（Unreached）、临时标号结点(Temporarily Labeled)和永久标号结点(Permanently Labeled)
三种类型。求解源点s到其他所有结点的最短路径的基本过程如下：
1）初始化。对所有结点V i，如果V i不等于V 0，则d (i )=∞, s (i)= Unreached；否则，d
(i)=0, s(i)= Temporarily Labeled。T←N，如果T为空，则算法结束。
2）从T标号点中选出加权距离最小的点V j。
d (j)=min{d (i), V i∈V-S}；s(j)= Permanently Labeled.
V j就是当前求得的一条从v0出发的最短路径的终点。令 S=S∪Vj.
3）对与V j相连的每个结点V k, V k∈V-S。如果d(j)+w(j,k)< d(k)，则修改d(k)为d(k)=
d(j)+w(j,k)。s(k)= Temporarily Labeled
4）重复操作2),3）共n -1 次。由此求得从V0 出发到图上各个结点的最短路径是依路径
权值递增的序列[6]。
优化途径分析
从上述算法描述过程可知，第2)、3)步是影响该算法效率的关键。由于每次搜索最小权
值的结点V j，都需要对V−S集合上的所有结点进行扫描，而这些结点是无序存放在一个链表
或数组中，会花费大量的时间；另外，搜索最小权值的过程中，还会出现某些结点被多次访
问的情况，增加了额外的运算量。
要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边的权值进行顺序排
列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率。这也是目前各种
基于传统的Dijkstra算法的各种优化算法的重要出发点之一。另外一个优化途径就是减少路
线分析过程中搜索结点的数量，从而尽快到达目标点。
另外，针对铁路网进行中转径路计算，就必须首先将铁路网按结点和边的关系抽象为图
的结构，即构建网络的拓扑关系。如果用矩阵来表示这个网络，不但所需空间巨大，而且效
率会很低。下面主要就如何用一个简洁高效的结构表示网的拓扑关系以及算法运行结构的实
现进行讨论。
2. 铁路客运网络拓扑结构描述
铁路客运网络的存储结构
网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示。一般而言，无向
图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表和十字链表表示，其优缺
点的比较见表 1[3]。
最短路径搜索问题一般都采用结点-弧结构的存储结构表示。这一方面清晰地表达了网
络的拓扑结构, 另一方面更加便于Dijkstra 算法的实现。采用邻接表类型存储交通网络拓扑
数据结构, 在业界早已达成共识。
- 3 -
表1 几种图的存储结构的比较
铁路客运中转问题，既与线路、车站、站间距离的铁路网信息相关，同时又与车次始发
车站、终到车站、中途停靠车站及到开时刻等车次信息相关。所需构建的铁路客运网络存储
结构要同时包含路网和开行车次。
本文采用车次-到站邻接表作为铁路客运网络的存储数据结构。表头结点存储指定指定
日期内有效的经过本站停靠的所有列车车次信息；头结点存储到站为某一指定站的信息；
表内结点某车次某停靠站的信息。表结点列出所有本站可达的换乘中转站，根据不同的表头
结点可以得到同站的车次序列。这样，车次-到站邻接表就表达了包含车站和车次信息的可
达铁路客运网络图,如图1所示[5]。
图1 车次-到站邻接表
铁路客运网络的层次编码
当一个人站在全国铁路客运运营示意图前，可以很快地找到其中两个车站间的一条径
路。这条径路即使不是最短或最优的，也是比较合理的一条径路。这时，人类的思维方法中
的层次策略、方向策略、贪心策略帮助我们快速找到一条径路。层次策略会使他优先选择经
过较大且可供选择的中转车次较多的车站；方向策略会使他选择趋向于终点站的径路；贪心
策略会使他选择趋于直线的线路。
层次策略是人类思维活动的一种重要方式，在解决具有空间特征的问题中常常被采用。
层次空间推理是根据一定规则将问题按空间或任务划分来进行推理的空间分析方法。划分具
有层次结构的空间对象是分层或分区进行的，每个层次或子区的对象具有相同结构、类型或
操作。层次 i+1 是层次 i 的空间子集。层次空间中的对象、对象间关系及其操作仅与被划分
成不同层次的同一任务有关[2]。例如，在铁路客运中转问题中对客运网络划分的层次的依据
就是中转的便捷程度，具体的就是车站始发、通过的车次的数量。
在铁路客运网络中提取以下车站：
1） 所有车次的始发车站、终到车站，记为 S1；
名 称 实现方法 优点 缺点 时间复杂度
邻接矩阵 二维数组 易判断两点间关系；易求顶点
的度
占用空间大 O(n2+m*n)
邻接表 链表 节省空间；易求顶点出度 不易判断两点间关系；不易求顶
点入度
O(n+m)或 O(n*m)
十字链表 链表 空间要求较小；易求得顶点的
度
结构较复杂 同邻接表
邻接多重表 链表 节省空间；易判断两点间的关
系
结构较复杂 同邻接表
- 4 -
2） 所有省会（直辖市、自治区首府）所在地车站,记为 S2；
3） 所有铁路局所在地、分界口车站, 记为 S3；
4） 所有客运线路中 3 条及以上线路相交的车站, 记为 S4；
5） 所有铁路客运结算站, 记为 S5。
分层表示的铁路客运网络层次图为：
1） 高层图：结点由 S1 S∪ 2 S∪ 3 S∪ 4 S∪ 5组成，边由所有车次被 S1 S∪ 2 S∪ 3 S∪ 4 S∪ 5
分割成的区间组成；
2） 子图：按照各铁路局管辖范围划分，包括辖区内的车站、线路、车次；
根据起点站 Vs、终点站 Vt 所位于的层次，通过层次图进行径路查询有 4 种情况：
1）起点站、终点站都位于高层图，仅需在高程图查询径路，遍历的结点数仅为近 300
个；
2) 起点站位于高程图，终点站不在高程图。首先需要遍历终点站所在子图，得到与终
点站相邻的高程图结点集{Vk}；然后在高层图中查询起点站 Vs 到{Vk}中各点的最短路，取
最小值；
3）起点站不在高程图，终点站位于高程图。方法同 2）；
4）起点站、终点站都不在高程图。分别求得与起点站、终点站相邻的高程图结点集，
再进行 1）。
通过层次图进行最短路查询，有效地减少了需要遍历的结点数量，可以提高算法的运行
效率。
3. 对 Dijkstra 算法运行结构的优化
当前流行的最短路算法运行结构分析比较
最短路算法运行数据结构纷繁多样，各有特色，主要有桶结构法、队列法以及堆栈实现
法。DIKBA 、DIKBD 以及 2que 在这方面是比较典型的代表。2que 虽然是基于图增长理论
的，但是快速搜索技术同样是其算法实现的关键，它用两个 FIFO 的队列实现了一个双端队
列结构来支持搜索过程。
DIKBA 和 DIKBD 是采用如图 2 所示的桶结构来支持这个运算，其算法的命名也来源
于此。在 DIKBA 算法中，第 i 个桶内装有权值落在［b*i, b * (i+1)］范围内的可供扫描的点，
其中 b 是视网络中边的权值分布情况而定的一个常数。每一个桶用队列来维护，这样每个点
有可能被多次扫描，但最多次数不会超 b 次。最坏情况下，DIKBA 的时间复杂度将会是
O(m*b+n(b+C/b))，其中，C 为图中边的最大权值。
DIKBD 将点按权值的范围大小分装在两个级别的桶内，高级别的桶保存权值较大的点，
相应的权值较小的点都放在低级别的桶内，每次扫描都只针对低级别桶中的点。当然随着点
的插入和删除，两个桶内的点是需要动态调整的。
在 DIKBA 算法中，给每个桶一定的范围以及 DIKBD 中使用双桶，在一定程度上都是
以空间换时间的做法，需要改进[3]。
- 5 -
图2 桶结构示例
在GIS领域，实现网络分析功能也多是基于各种运行结构的Dijkstra算法。如Arc/Info中
的Network 采用二叉堆优先级队列来实现Dikstra算法; Geo star的网络分析采用快速排序的
FIFO 队列来实现Dijkstra算法[6]。这几种算法均采用了拓扑邻接表的存储数据结构[4]。
Arc/Info和MapInfo均不存储网络的拓扑结构。选定正确的网络存储结构后, 需要设计出精致
的算法运行结构, 这也是最短路径算法研究的热点所在。
表2列出了主要的最短路算法的运行结构。
表2 主要最短路算法的运行结构
基于堆排序的铁路客运中转径路优化算法
针对铁路客运中转径路优化问题，本文对临时标记结点采取堆排序方法，将结点最短路
径值作为堆排序的关键字，采用堆排序有如下考虑：
1)充分利用了现有堆数据，大大降低了数据比较的频率。堆排序的主要运行时间消耗在
建初始堆上，而对于 Dijkstra 算法来说，整个最短路径的搜索过程中进行的 n 次堆排序只需
要建一个堆，从而明显克服了堆排序的主要缺点，使堆排序的优势更加明显地发挥出来。
2)Dijkstra 算法中结点最短路径值的修改总是比原来的值小。Dijkstra 算法中采用小根堆
即堆顶元素为关键字值最小的元素。堆中某元素的关键字(即结点的最短路径值)修改后，进
行堆的重新整理操作时，只需要判断此元素是否需要和其父结点进行位置调整。所以 Dijk
stra 算法中堆的重新整理操作要比传统堆的重新整理过程简单、高效。
3)堆排序只需要一个记录大小的辅助空间。快速排序需要 O(logn) 的辅助存储空间，而
归并排序则需要 O(n)的辅助存储空间。
4. 总结
最短路 Dijkstra 算法应用领域十分广泛。本文针对铁路客运中转径路优化问题，在分析
经典最短路 Dijkstra 算法的思想和优化途径的基础上，引入最短路 Dijkstra 算法来求解该问
题。在铁路客运网络拓扑结构描述上，采取车次—到站邻接表的数据结构，同时结合业务逻
算法名称 运行结构
2Que 两个 FIFO 的队列实现一个双端队列结构来支持搜索过程
DIKBA 第 i 个桶内装有权值落在［b*i,(i+1)*b)范围内可供扫描的点
DIKBD 将点按权值大小分装在两个级别桶内
ArcInfo Network 二叉堆优先级队列
Geo star 快速排序的FIFO 队列
- 6 -
辑对客运网络采取层次策略建立层次图；在比较分析流行的最短路 Dijkstra 算法运行结构的
基础上，提出了采用堆排序的方法来的搜索过程的临时结点进行“松弛”操作，有效提高了搜
索具有最小权值的结点的效率。
参考文献
[1] CHERKA SSKYBV, GOLDBERGAV, RADZIKT. Shortest Paths Algorithms: Theory and Experimental
Evaluation [J]. Mathematical Programming. 1996,73: 129-174.
[2] .吴京,景宁,陈宏盛. 最佳路径的层次编码及查询算法. 计算机学报,2000,23(2): 184-186.
[3] 乐阳等. Dijkstra 最短路径算法的一种高效率实现. 武汉: 武汉测绘科技大学学报, 1999,24(3): 62-64.
[4] 陆锋. 最短路算法:分类体系和研究进展. 北京: 测绘学报,2001,30(8):269-273.
[5] 吕晓燕等. 基于车次径路约束下的客运径路生成算法优化. 北京,中国铁道科学,2007,28(5):122-124.
[6] 严蔚敏, 吴伟民编著. 数据结构(C 语言版). 北京: 清华大学出版社, 1997.
Optimization of Transfer Route in Railway Passenger
Transportation Based On the Dijkstra Algorithm
Yu zhenjiang, Wang Chengliang
College of Software Engineering, Chongqing University, Chongqing（400044）
Abstract
Railway passenger transfer optimization approach is to find the optimal path algorithm based on rail
transport network topology. Because of the context of practical application, conditions and restrictions
of the optimal path algorithm are much more complicated than those of the classic shortest path
algorithm. But the core idea of railway passenger transfer optimization approach is derived from
classical shortest path algorithm. Based on the original Dijkstra algorithm, the algorithm and data
structure has been improved in this paper. Combining with the area of application, this new
optimization method encodes the railway network according to hierarchical nodes, and aggregates the
business logic into the search process, to achieve the efficiency of the algorithm and the effectiveness
of search path.
Key words: Shortest path; Dijkstra algorithm; Railway network; Route computation
作者简介：
余震江（1978-），男，硕士研究生，主要研究方向：Web 开发技术、数据库技术、交通信息
化。
王成良（1964-），男，教授，博士，主要研究方向：Web 开发技术、数据库与数据挖掘、企
业信息化。
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /All
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB )
/CalCMYKProfile (. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB )
/CannotEmbedFontPolicy /Warning
/CompatibilityLevel
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/ColorConversionStrategy /LeaveColorUnchanged
/DoThumbnails false
/EmbedAllFonts true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveEPSInfo true
/PreserveHalftoneInfo false
/PreserveOPIComments false
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageDownsampleThreshold
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageDownsampleThreshold
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
]
/PDFXOutputIntentProfile ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /Unknown
/Description <<
/FRA <FEFF004f007000740069006f006e00730020007000650072006d0065007400740061006e007400200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000500044004600200064006f007400e900730020006400270075006e00650020007200e90073006f006c007500740069006f006e002000e9006c0065007600e9006500200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200061006d00e9006c0069006f007200e90065002e00200049006c002000650073007400200070006f0073007300690062006c0065002000640027006f00750076007200690072002000630065007300200064006f00630075006d0065006e007400730020005000440046002000640061006e00730020004100630072006f0062006100740020006500740020005200650061006400650072002c002000760065007200730069006f006e002000200035002e00300020006f007500200075006c007400e9007200690065007500720065002e>
/ENU (Use these settings to create PDF documents with higher image resolution for improved printing quality. The PDF documents can be opened with Acrobat and Reader and later.)
/JPN <FEFF3053306e8a2d5b9a306f30019ad889e350cf5ea6753b50cf3092542b308000200050004400460020658766f830924f5c62103059308b3068304d306b4f7f75283057307e30593002537052376642306e753b8cea3092670059279650306b4fdd306430533068304c3067304d307e305930023053306e8a2d5b9a30674f5c62103057305f00200050004400460020658766f8306f0020004100630072006f0062006100740020304a30883073002000520065006100640065007200200035002e003000204ee5964d30678868793a3067304d307e30593002>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e0020005000440046002d0044006f006b0075006d0065006e00740065006e0020006d00690074002000650069006e006500720020006800f60068006500720065006e002000420069006c0064006100750066006c00f600730075006e0067002c00200075006d002000650069006e0065002000760065007200620065007300730065007200740065002000420069006c0064007100750061006c0069007400e400740020007a0075002000650072007a00690065006c0065006e002e00200044006900650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f0062006100740020006f0064006500720020006d00690074002000640065006d002000520065006100640065007200200035002e003000200075006e00640020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/PTB <FEFF005500740069006c0069007a006500200065007300740061007300200063006f006e00660069006700750072006100e700f5006500730020007000610072006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000500044004600200063006f006d00200075006d00610020007200650073006f006c007500e700e3006f00200064006500200069006d006100670065006d0020007300750070006500720069006f0072002000700061007200610020006f006200740065007200200075006d00610020007100750061006c0069006400610064006500200064006500200069006d0070007200650073007300e3006f0020006d0065006c0068006f0072002e0020004f007300200064006f00630075006d0065006e0074006f0073002000500044004600200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002c002000520065006100640065007200200035002e0030002000650020007300750070006500720069006f0072002e>
/DAN <FEFF004200720075006700200064006900730073006500200069006e0064007300740069006c006c0069006e006700650072002000740069006c0020006100740020006f0070007200650074007400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006d006500640020006800f8006a006500720065002000620069006c006c00650064006f0070006c00f80073006e0069006e006700200066006f00720020006100740020006600e50020006200650064007200650020007500640073006b00720069006600740073006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e006500730020006d006500640020004100630072006f0062006100740020006f0067002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/NLD <FEFF004700650062007200750069006b002000640065007a006500200069006e007300740065006c006c0069006e00670065006e0020006f006d0020005000440046002d0064006f00630075006d0065006e00740065006e0020007400650020006d0061006b0065006e0020006d00650074002000650065006e00200068006f0067006500720065002000610066006200650065006c00640069006e00670073007200650073006f006c007500740069006500200076006f006f0072002000650065006e0020006200650074006500720065002000610066006400720075006b006b00770061006c00690074006500690074002e0020004400650020005000440046002d0064006f00630075006d0065006e00740065006e0020006b0075006e006e0065006e00200077006f007200640065006e002000670065006f00700065006e00640020006d006500740020004100630072006f00620061007400200065006e002000520065006100640065007200200035002e003000200065006e00200068006f006700650072002e>
/ESP <FEFF0055007300650020006500730074006100730020006f007000630069006f006e006500730020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f0073002000500044004600200063006f006e0020006d00610079006f00720020007200650073006f006c00750063006900f3006e00200064006500200069006d006100670065006e00200070006100720061002000610075006d0065006e0074006100720020006c0061002000630061006c006900640061006400200061006c00200069006d007000720069006d00690072002e0020004c006f007300200064006f00630075006d0065006e0074006f00730020005000440046002000730065002000700075006500640065006e00200061006200720069007200200063006f006e0020004100630072006f00620061007400200079002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/SUO <FEFF004e00e4006900640065006e002000610073006500740075007300740065006e0020006100760075006c006c006100200076006f0069006400610061006e0020006c0075006f006400610020005000440046002d0061007300690061006b00690072006a006f006a0061002c0020006a006f006900640065006e002000740075006c006f0073007400750073006c00610061007400750020006f006e0020006b006f0072006b006500610020006a00610020006b007500760061006e0020007400610072006b006b007500750073002000730075007500720069002e0020005000440046002d0061007300690061006b00690072006a0061007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f006200610074002d0020006a00610020004100630072006f006200610074002000520065006100640065007200200035002e00300020002d006f0068006a0065006c006d0061006c006c0061002000740061006900200075007500640065006d006d0061006c006c0061002000760065007200730069006f006c006c0061002e>
/ITA <FEFF00550073006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000500044004600200063006f006e00200075006e00610020007200690073006f006c0075007a0069006f006e00650020006d0061006700670069006f00720065002000700065007200200075006e00610020007100750061006c0069007400e00020006400690020007300740061006d007000610020006d00690067006c0069006f00720065002e0020004900200064006f00630075006d0065006e00740069002000500044004600200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f00700070007200650074007400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006d006500640020006800f80079006500720065002000620069006c00640065006f00700070006c00f80073006e0069006e006700200066006f00720020006200650064007200650020007500740073006b00720069006600740073006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e006500730020006d006500640020004100630072006f0062006100740020006f0067002000520065006100640065007200200035002e00300020006f0067002000730065006e006500720065002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006e00e40072002000640075002000760069006c006c00200073006b0061007000610020005000440046002d0064006f006b0075006d0065006e00740020006d006500640020006800f6006700720065002000620069006c0064007500700070006c00f60073006e0069006e00670020006f006300680020006400e40072006d006500640020006600e50020006200e400740074007200650020007500740073006b00720069006600740073006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e0020006b0061006e002000f600700070006e006100730020006d006500640020004100630072006f0062006100740020006f00630068002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006100720065002e>
>>
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [ ]
>> setpagedevice
