论文基于Dijkstra算法的列车进路选择，本文是算法类有关毕业论文提纲范文与Dijkstra算法和列车和列车进路选择类电大毕业论文范文.
杨龙平 柳州铁道职业技术学院
【摘 要】 在计算机联锁中,列车进路的算法设计是最关键的环节,它关系到列车的运行安全和车站通过能力的提高.Dijkstra 算法能够计算出无向图中某个任意结点到其它所有结点之间的最短路径,给车站及咽喉区提高通过能力提供了可能性.如果把车站用无向图来表示,车站设备的占用状态信息融合到算法中,就可以很方便地实现利用计算机来选择列车的进路.
【关键词】 无向图 列车进路 权值 Dijkstra 算法 最短路径
列车在车站内运行的路径,称为进路.在进路上包含有很多的信号设备,如信号机、轨道电路、道岔等.为了保证安全,必须在列车进出站作业之前要把进路准备好,且要使进路上的信号设备锁定选择状态,以预防敌对进路的产生[1] .随着铁路信息化的深入,计算机联锁得到广泛的应用,研究利用计算机来选择列车进路的算法也越来越多,利用最短路径的方法来探讨列车进路的选择,可提高车站的通过能力.
一、铁路车站的网络拓扑构建
1.1 车站拓扑结构
车站是*接发列车、调车作业的场所,根据列车作业的需求量,在车站内设置有一定数量的配线[2] ,这些配线之间的切换是通过道岔来实现.为了能够对车站的网络拓扑进行描述,进行如下的定义：（1）分岔结点：把连接不同线路的点称为分岔结点,比如道岔、交叉渡线的中心点.（2）直连结点：同一条线上连接两个不同轨道电路区段的结点.
依据定义,假如有车站网络拓扑[3] ,如图 1 所示.
图 1 中的直连结点主要是由同一条线路上不同的轨道电路区段产生,在车站的两端和股道上.为了*接发列车作业,设置有一定数量的按钮,这些按钮也生成了直连结点.分岔结点主要是由道岔产生, 其中在右侧咽喉区有交叉渡线,需要设置一个中心点构成的分岔结点.不管是接发列车还是调车作业,列车在车站中的运行方向是双向,符合图论中无向图的定义要求,因此,车站的平面图实际上是一个无向图.由图 1 可知,图中的任意两个结点之间都是连通的,它是一个强连通图.
1.2 列车进路与最短路径
*列车进路的方法是先按下始端按钮,再按下终端按钮,就会自动生成从始端按钮到终端按钮的通路,因而,排列进路的实质是在两个已知结点之间寻找一条通路,这条通路最好是最短路径,以利于提高车站的通过能力.但要避免下列路径的产生,如图 2 所示.
图 2（a）进路 r1 和 r2 同一时间占用了同一个区段,所以是敌对进路[3] .因为道岔的构造原因,列车在运行时,为了保证运行安全,不能同时经由一组道岔的定位和反位,交叉渡线上的中心点也不能拐弯,只能直行,所以图 2 的（b）和（c）所示的进路不允许*.对于一个全连通图,任意两个结点之间都存在一条路径[5] ,要找出一最短路径,其目的是这个生成树上各边的代价之和是最小的.在车站的网络拓扑图中,找出最短路径,主要是有利于提高车站的通过能力,也即每次作业占用设备的时间最少.影响车站的通过能力特别是咽喉区的通过能力,主要因素是各种作业占用设备的标准时间.把第 i 个结点的标准时间称为 ti,任意两个结点称为 vi 和 vj,结点之间的边 Eij 的权值为这两个设备的标准作业时间之和,也即
Uij ＝ ti ＋ tj （公式 1）
当然,影响咽喉区通过能力的因素还有其它,比如车站技术设备状况、运行图和车站作业之间的协调等[2] ,不管是何种因素,最后都能够通过增加或减少作业的标准时间来实现.为了讨论问题的方便,对结点进行连续编号,假设每个结点的标准作业时间如表 1 所示.根据表 1 的作业时间,依据公式 1,可以计算出图 1 的带权值的无向图,如图 3 所示.列车进路的选择, 其实质是在两个已知点之间寻找一条通路,这条通路之间占用设备的时间总和最小.比如,*从结点1 至结点 14 的接车进路,经过由结点 1、3、6、7、9、11、13、14 构成的路径所耗费的时间总和最小.
二、Dijkstra 算法与列车进路的数据设计
2.1 Dijkstra 算法的基本应用
对一个具有 n 个顶点和 e 条边的图 G,Dijkstra 的解决思路：按照从源点到其余每一顶点的最短路径长度的升序,依次求出从源点到各顶点的最短路径及长度.每次求出从源点 i 到一个终点 j 的最短路径及长度以后,把该顶点 j 作为新的中间点,用 vi~vj 的最短路径和最短路径长度对 vi 到其它还没求出最短路径的那些终点的当前最短路径及长度进行修改, 让其成为当前的最短路径和最短路径长度, 当进行n－2 次后算法结束[6] .设定一个集合假定为 Set,用来保存已经求出的最短路径的终点序号,它的初值中只有一个元素（源点 i）.以后每求出一个从源点 i 到终点 j 的最短路径,就将该顶点 j 并入 Set 集合,同时把 j 作为新的中间点.还需要设置一个整型数组 list[n],该数组中的第 k 个元素 list[k] 用来保存从源点 i 到终点 k 的目前最短路径长度,它的初值为（i,k）边上的权值,如果没有边,权值为 MaxValue.在运算过程中,每考虑一个新的中间点,list[k] 的值可变小.再设置一个与 list 数组对应的、类型为指针的邻接链表表头向量数组path,该数组的第 k 个元素 path[k] 指向一个单链表,该单链表中保存着从源点 i 到终点 k 的目前最短路径（顶点序列）.如果 vi-vk 之间存在着一条边,则 path[k] 初始指向由顶点 i和 k 构成的一个单链表,否则 path[k] 的初值为 NULL.
有图 4 所示的无向图, 来说明 Dijkstra 的算法运算过程.
利用 set[n] 来保存已经求得的最短路径各终点,set[k] 取值 1 表示顶点 k 已经在集合中,否则取值 0,初始状态如表2 所示.
第一次运算,求出从源点 1 到第 1 个终点的最短路径.首先从 set 元素取值为 0 的对应 list 元素中,查找出值小的元素,求得 list[3] 的值最小,所以第一个终点为 3,最短距离为 list[3]等于13,最短路径为 path[1]等于{1,3}.把 set[3] 置为 1,并入到 set 集合,然后再以结点 3 为新的中间点,对 set 数组中元素为 0 的每个顶点 j 的当前最短路径 list[j] 和当前最短路径 path[j] 进行必要的修改,如表 3 所示.
第二次运算,求出从源点 1 到第二个终点的最短路径.首先从 set 数组中取值为 0 的对应 list 元素中,查找值最小的元素,求得 list[4] 的值最小,第二个终点为结点 4,最短距离为 list[4] ＝ 21,最短路径为 path[4] ＝｛1,3,4｝.把 set[4] 置 1,以结点 4 为新的中间点,对 set 集合外的顶点list[j] 和 path[j] 进行修改,如表 4 所示.
2.2 列车进路的数据定义
（1）车站结点的数据定义.由图 2 所示的无向图可知,最复杂的结点为分岔结点中的交叉渡线中心点,连接有四个方向,其次是分岔结点中的道岔,连接有三个方向,其中有两个方向分别表示反位和定位；直通结点的只用来连接前和后两个方向.因而结点的数据类型定义如下：
Struct SwitchNode {
int num; // 存储结点号
int occupy; // 是否被占用
int search; // 是否搜索过
int id; // 结点的类型,取值为 1 － 3
SwitchNode *back, *front, *right, *left; // 连接四个方向的下一个结点地址
int sback,ront,sright,sleft; // 每一分支与下一个连接点的权值
（2）数组的定义.因为进路的选择实际上是在两个已知点之间寻找一条通路,起始结点（v 0 ）和进路的终点（v k ）是固定的结点.为了能够方便地定位到 v 0 结点,需要设置数组 sw[n],用来存储每一个结点的地址,所以,利用 Dijkstra算法来选择列车进路,就是在两个已知点之间寻找一条代价最小的通路.根据 Dijkstra 算法的要求,需要定义 set[n] 来存储已经求得的终点的集合；定义 list[n] 用来保存从源点 i到终点 j 的当前最短路径长度；定义 path 为邻接表表头向量数组,用来存储结点 i 到任意结点 j 经历的所有结点号,它实际是邻接链表中每一个单链表的头指针.
三、列车进路的 Dijkstra 算法实现
在进行算法设计时,要考虑这么几个原则,一是保证进路的代价最小,二是要避免敌对进路,三是要避免“人”字型和 “Z” 字型进路. 因而, 算法的主要思路： （1） 算法从 “start”结点开始,对其它的 set[i] 进行置 0 初始化,把 set[start] 进行置 1.（2）计算 start 结点的邻接边,如果邻接边的下一个结点 i 已经被占用,在计算路径长度时,该邻接边被忽略,否则把该邻接边的权值加到当前路径中.（3）找出当前所有 set[i] 为 0 的结点的路径中最小的值,把它作为最短路径,把该结点当作为第 1 个终点,并入到 path 中.（4）如果所有结点已经被标记完（set[i]等于1）,则程序结束,否则开始第（5）步骤.（5）判断当前终点 i 的类型以及前一结点进入该结点的支路,如果是直连结点,可以计算任何一条支路；如果是道岔结点, 则从left或right进入的结点, 不能相互加权 ；如果是中心结点,left 和 back 可以相互加权,front 和 right 可以相互加权.（6）把加权后的值分别与原来的值进行比较,如果小于原来的值, 则进行替换. （7） 对路径 path 进行修改,转到步骤（3）.算法设计如下：
void dijkstra(SwitchNode sw, EdgePath path,int list[],int start,int end) {
int j,k,w,m,t,t1,t2;
int *set等于new int[n];
SwitchNode *temp,*tp1,*tp2;
for(j等于1;j<等于n;j++) {
if(j等于等于start) set[j]等于1;
else set[j]等于0;
list[j]等于MaxValue; temp等于sw [start];
if( 当前结点没有被占用 ) {
if( 与当前结点相连的其它节点不为 null&& 当前值为与之相邻的下一个结点号 )
让当前结点分别指向它的邻接点；
}
if( 当前结点不是开始结点 && 结点权值小于已经存在的权值 ) {
初始化当前节点的 path 路径；
}
else path[j]等于NULL;
}
for(k等于2;k<等于n-1;k++) {
w等于MaxValue; m等于start;
for(j等于1;j<等于n;j++)
if(set[j]等于等于0&&list[j]<w) { w等于list[j]; m等于j; }
if(m！等于start||sw[m]->occupy！等于0) set[m]等于1;
else break;
for(j等于1;j<等于n;j++)
if(set[j]等于等于0) {
temp等于path[m];
找出结点 m 的前继结点编号,保存到 t 中；
switch(sw[m]->id) { // 识别“人”型和“z”型进路
case 1: // 直连接点
tp1等于sw[m]->back; tp2等于sw[m]->front;
if(( 前继结点 t 从 back 接入 || 前继结点 t 从 front 接入 )&& 没有被占用 )
if( 已知权值大于某个结点到该结点的权值 )
修改当前结点的权值；
break;
case 2: // 如果是道岔结点,left 和 right 入口不能相互计算权值
tp1等于sw[m]->right; tp2等于sw[m]->left;
if( 前继结点是从 front 进入 && 没有被占用 )
if(分别计算left和right权值, 已知权值大于到该结点的权值)
修改当前结点的权值；
temp等于sw[m]->front;
if( 前继结点 t 是从 left 或者 right 进入 && 没有被占用 )
if( 只对 front 计算权值,已知权值大于到该结点的权值 )
修改当前结点的权值；
break;
//front 和 right、left 和 back 可以互为计算权值
case 3: // 如果是交叉渡线
temp等于sw[m]->right;
if( 交叉渡线的前继结点分别是哪一个 && 没有被占用 )
if( 当前路径的权值与相应前继节点的权值累加和 )
修改当前路径及权值；
break;
}
PATH(path,m,j);
}
}
void PATH(EdgePath path,int m,int j) { // 生成最短路径算法
EdgePath *p,*q,*temp;
p等于path[j];
while(p！等于NULL)
{ path[j]等于p->next; delete p; p等于path[j]; }
p等于path[m];
while(p！等于NULL) {
q等于new EdgePath; q->vex等于p->vex;
if(path[j]等于等于NULL) path[j]等于q;
else temp->next等于q;
temp等于q; p等于p->next;
}
q等于new EdgePath; q->vex等于j; q->next等于NULL; temp->next等于q; // 并入新结点
}
结论：无向图的结点之间的权值是由设备占用时间计算得来,在实际工作中,设备占用的标准时间受作业的性质、技术手段等多种因素的影响,设备占用的时间越长,权值就会越大.另外,由于列车通过道岔定位的速度比通过道岔反位的速度要快,因而,在进行权值设定时,可以通过适当增加设备占用时间来加大道岔反位时的权值,以确保同等条件下优先选择道岔定位,以提高咽喉区通过能力.
上文点评,该文是关于Dijkstra算法和列车和列车进路选择方面的相关大学硕士和算法本科毕业论文以及相关算法论文开题报告范文和职称论文写作参考文献资料.
参考文献：
1、 高等教育利益相关者理论的进路 摘 要利益相关者理论被广泛地引入高……教育研究,成为分析高……教育问题的新视域 高……教育领域引入利益相关者理论是高……院校外部环境变化以及高……院校类企业行为使然 关于高……教育利益相关者的研究为高.
2、 我国高等教育管理的范式变迁和进路 中图分类号G647 文献标识码A DOI10 16871j cnki kjwha 2018 10 055摘要自新中国成立以来,我们国家的教育历经了很多变革,而这其中,关于我国的高……教育这一方面的管理.
3、 有机马克思主义形成的两条进路与其不同理论取向 〔作者简介〕杨富斌（1958—）,男,河北省邯郸市人,北京第二外国语学院国际法学院教授,研究方向为马克思主义哲学和现当代西方哲学 〔摘要〕有机马克思主义的形成有两条进路 一条进路是从福斯特.
4、 新媒体时代大学生法治精神培养的丰厚意蕴和有效进路 摘要大学生法治精神培养是促进大学生价值取向、行为模式健康发展的有效方式 然而,现阶段高校在培养大学生法治精神方面却存在很多的问题 本文从科学认识大学生法治教育的丰厚意蕴出发,在剖析大学生法治教育存在问.
5、 中国特色党政关系构建的理论背景、历史进路和新趋势 崔言鹏,高新民（党校 党建部,北京100091）摘要党政关系问题是中国特色社会主义建设的重要问题,其调整与改革是我国政治文明建设的核心内容 中国在分析西方执政党党政关系理论模型和马克思主义经典作家党政.
6、 王懋竑《家礼》辨伪的逻辑进路和思想意义 【摘要】家礼是否为朱熹所作,是元明以来儒者聚讼纷纭的学术公案 清儒王懋竑以精于朱学著称,撰作家礼考家礼后考家礼考误诸篇以证家礼非朱熹之书,在清代学术史、朱子学研究领域影响深远 近百年来,学者虽多反驳王.