关于如何存储信息已经在上一节说过，这里就不重复了，简单回顾一下实现内容。由于新人不知道blog到底能发多长，所以还是麻烦有需求的看官Tp到前一节：【Java实现】南京地铁导航系统的简单实现（一）—— 存储站点信息_kksp993的博客-CSDN博客
目录
实现内容
问题分析
算法的选择
权值向量表的设计
Floyd权值向量表
多段图权值向量表
三种要求下的算法设计（一）—— 站点少
权值向量表的确定
三种要求下的算法设计（二）—— 换成少
模型的修正
权值向量表的确定
三种要求下的算法设计（三）—— 用时少
模型的修正
路径的回溯
对于Floyd算法的回溯
对于动态规划的回溯
实现内容
以南京地铁运营示意图为模板，实现任意两个站点之间最优路径导航的规划与动态展示效果。具体模板图片以及要求如下：
1. 存储南京地铁线路站点信息。
2. 给定起点站和终点站，假设相邻站点路径长度相等，求路径最短的地铁乘坐方案；
3. 给定起点站和终点站，假设相邻站点路径长度相等，求换乘次数最少的地铁乘坐方案，若存在多条换乘次数相同的乘坐方案，则给出换乘次数最少且路径长度最短的乘坐方案。
4. 在实际应用中，相邻站点的距离并不相等，假设中转站地铁停留时间为T1，非中转站地铁停留时间为T2，地铁换乘一次的时间消耗为T3（不考虑等待地铁的时间），地铁平均速度为v，相邻站点的路径长度已知，试求：在给定起点站和终点站的情况下，求乘坐时间最短的地铁乘坐方案。
5. 设计可视化的查询界面,对以上内容进行动态化展示。
问题分析
很显然，这5个步骤是按照难度由浅入深来的，可以分为如下层层递进关系：
（1）经过站点最少：经过站点最少可以采用数起始终点的经由站点个数加以实现
（2）换乘次数最少：换成最少则可以化归为对上述站点最少中换乘做一个大的惩罚项处理；
（3）理论用时最短：需要分别计算等待用时、换乘用时、运行用时等诸多因素，对上述过程进行修正。
这个题目层层递进，显然需要使用化归的手法，接下来我们具体分析使用的方法。
算法的选择
常规的算法选择一般为：迪杰斯特拉算法、弗洛伊德算法。
迪杰斯特拉算法：【优点】复杂度较Floyd算法低，为O(e·logv)。
【缺点】因为每次查询都需要重新去经过算法的每一环节，响应时间长。
【相关算法传送门】 单源最短路 Dijkstra 算法原理详解、代码实现和复杂度分析_Alan-zzx的博客-CSDN博客_dijkstra算法复杂度
弗洛伊德算法： 【优点】可以通过一次求取路由矩阵和路由开销保存下来使用，直到更新地图才需要修正。
【缺点】求取时间过长：，且保存较大非稀疏矩阵无疑增加了开销。
【相关算法传送门】 最短路径模板+解析——（FLoyd算法）_ytuyzh的博客-CSDN博客_floyd算法
这两种方法都是长期被使用的优秀的方法，我们需要借鉴。但是，所谓的借鉴绝对不是照搬，需要理解其中的精髓，明白它的核心，有思考的去运用。“一切从实际出发，实事求是”说的没错，别人的图长得和我们一样吗？我们直接用就一定最好吗？都不见得的。因此要根据具体的情况详细分析，不能抱着本本主义去照抄照做，这样是不会有进步的。看清问题的实质是帮助我们解决问题的最佳捷径，在没有看清楚问题本质的情况下贸然去套公式，只会是光谱抗性药，不可能是靶向性的特效药，效果虽有，但肯定没有特效药好。这便是作用范围和效果的权衡了，鱼和熊掌不可兼得。既然题目具体，那么为何不用“特效药”呢？
闲话不说，我们很容易发现地铁线路图有如下鲜明特征：
（1）地铁主要由极少数中转站构成，几乎占比只有10%
（2）地铁非中转站只能双向行驶，对于有目的性的乘客而言只是单向通行。这意味着邻接矩阵十分稀疏。
（3）地铁对每种线路换乘与否十分考究，因此普遍最短路径计算需要特殊处理。
由此我们把握住中转站很少、非中转不转弯这两个特征，即可认为：非中转之间的开销可以看作一个整体。这样一来，需要关注的节点只有中转站那不到20个了，其余均隐含在边的权值信息里去了。
结合了题意再考虑上述过程，弗洛伊德的开销将不再头疼——中转站数目稀少，复杂程度大大降低，大大节约了时间。因此整个问题简化为如下流程：
（1）从起点到达中转站
（2）中转站到达中转站的Floyd
（3）从中转站到达终点站
对于不需要换乘，或者仅换乘一次的需要特殊处理，因为可能不需要参考Floyd算法的结果。
接着我们思考，这三个步骤的做法，是不是很像动态规划算法里的多段图问题？从起始站出发为第0个阶段，起点处的中转站为第1个阶段，终点处的中转站为第2个阶段，终点站是第三个阶段。由于如果不需要换乘或者换乘较少可能会跳过步骤，那么统一流程应当不进行省略，而是将该步骤的开销置0即可。下图显示了多段图的含义以及算法流程图。
【相关算法传送门】 动态规划法解多段图最短路径问题 - 乌漆WhiteMoon - 博客园
权值向量表的设计我们需要提供两张权值向量表——Floyd权值向量表、多段图权值向量表。其中后者中与之间的权值向量需要参考前者Floyd算法结果。
Floyd权值向量表由于该算法记录中转站之间的权值向量，因此节点仅包括不到20个中转站；又因为该图为无向图，因此权值向量矩阵是一个对称矩阵，仅需单向填写权值向量表按主对角线复制即可。设中转站有m个，那么矩阵应当为m*m的对称矩阵。
多段图权值向量表考虑多段图权值向量表的组成：不难发现，主要关系的节点有、、、。将他们按序组成一行向量，设的数组长度为，的长度为，如下图所示：
这样以来，由上述行向量为标签的权值向量表应当是行列均为 的方阵。由于这是一个单源路径的计算，只需要回答一个方向的最短路线，且主对角线元素均为0，因此只用关心上三角矩阵（不包括主对角线）。若记录“-”表示不做关心（设为INFTY），*表示有数字，INF表示不可达，因此可初始化得到如下矩阵：
三种要求下的算法设计（一）—— 站点少 权值向量表的确定对的路径权重应为该路经由的边数，而对于不可达的二元对" src="https://latex.codecogs.com/gif.latex?%5Clarge%20%3CV_O%2CV_T%3E" />,其路径权值应当设置为无穷大：
三种要求下的算法设计（二）—— 换成少 模型的修正
很显然，换乘少是第一目标，而过站少则是第二目标。参加过高考的可能都会有这样的体会，在总分一样的情况下，依次优先计算数学成绩、英语成绩、语文成绩（每个省份可能不一样，我们的就不是这一套，不要在意这些细节）。这个时候系统是怎么计算的？看过那个最后录取分的人都明白：它会显示348.124139085（这是我随便写的，不要对号入座）。它看起来仅仅是把成绩分开来并排写了，为什么会有优先权的区分？原因在于它对分数进行了加权——相当于乘以一个权值向量。
那么，在我们的模型中如何强化这个换成少的目标呢？只要在真正换乘的地方，那一站设置一个惩罚项（很大的系数），那么计算过程中会优先得到强化的目标下的结果，非强化目标的影响有限化。具体而言，设Ts为换乘站， 代表OT路径上的边，目标函数可以表示成如下形式：
其中λ应当选择远大于单条线路长度的值，这里选择λ=100，当然越大越好。
（当时我保守选了10，然后翻车了...）
权值向量表的确定
对应权值向量表而言，需要将惩罚系数加在如下两个方面：
（1）Floyd权值向量表：初始化时，每一“*”需要额外增加一次换成损失λ。
（2）多段图权值向量表：对于第一次到达中转站和从中转站到达终点站需要增加换成损 失λ，由于经由线路数应当比换成次数多一次，所以可以考虑只记录的换成损失λ。（如果两者都考虑会与实际不符，但是对于程序运行结果而言没有影响）
三种要求下的算法设计（三）—— 用时少 模型的修正
在实际应用中，相邻站点的距离并不相等，需要考虑中转站地铁停留时间，非中转站地铁停留时间，地铁运行速度，每一站之间的地铁运行路程等诸多因素。依照题目要求简化模型，我们设定中转站地铁停留时间为T1，非中转站地铁停留时间为T2，地铁换乘一次的时间消耗为T3（不考虑等待地铁的时间），地铁平均速度为v，相邻站点的路径长度d。因此我们需要重新计算新约束下的权值矩阵。
查阅资料,可以得到了南京地铁各站点之间距离的信息表：南京地铁S7号线各站点间距表- 南京本地宝
站点索引
1/迈-药
2/油-经
3/林-秣
4/龙-仙
10/雨-安
s1/禄-南
s3/黄-南
s7/无-禄
s8/泰-金
s9/翔-高
1
1142
2631
2537
1574
1729
7926
1712
1229
1236
10003
2
1121
1622
1049
1828
1154
4234
1998
2261
2741
7374
3
1691
1262
1127
821
1427
7283
1350
1529
2830
11219
4
1061
1379
1407
1359
1134
4723
1471
2423
1401
16912
5
1254
1473
1854
807
833
3242
1324
5236
1829
6232
6
862
1312
3535
1391
4545
3252
2099
3138
2151
0
7
1147
1257
961
2018
1350
4077
9844
5502
3880
0
8
1125
1002
1845
1128
1512
0
1525
5486
1567
0
9
909
874
1379
2749
848
0
2007
962
2893
0
10
1914
745
2017
2569
1865
0
1037
0
2077
0
11
2093
1022
2851
2564
1400
0
949
0
2375
0
12
1455
1024
858
3233
1307
0
1154
0
1606
0
13
1283
1300
859
1187
2157
0
1187
0
1475
0
14
1076
1521
931
1938
0
0
1608
0
6112
0
15
1853
1307
1067
2454
0
0
1446
0
4971
0
16
2276
937
1308
2185
0
0
1507
0
5475
0
17
1345
1168
1143
3212
0
0
1470
0
0
0
18
904
2779
977
0
0
0
1963
0
0
0
19
1332
3015
1153
0
0
0
0
0
0
0
20
1475
1675
1137
0
0
0
0
0
0
0
21
1135
1326
1222
0
0
0
0
0
0
0
22
1919
1519
1105
0
0
0
0
0
0
0
23
1312
1066
1826
0
0
0
0
0
0
0
24
1550
1947
1791
0
0
0
0
0
0
0
25
2720
1846
2343
0
0
0
0
0
0
0
26
1964
0
1526
0
0
0
0
0
0
0
27
0
0
1301
0
0
0
0
0
0
0
28
0
0
2995
0
0
0
0
0
0
0
由于当前目标是使得用时最小，因此权值表内的权值应当存储两点之间的用时消耗。对于乘坐地铁的用时消耗可以分为以下几个部分：
I. 地铁运行时长：
II. 地铁停站等待时常：
III.地铁中转站额外消耗：
IV. 地铁中转换乘的额外消耗：
为了使得能与前两问具有相同的函数形式，得到能够适用三类问题的统一公式便于调用，对这四种函数进行了如下定义与统一:
路径的回溯 对于Floyd算法的回溯
一般网上和教科书上对于Floyd的路由矩阵记录有两种模式（比较常见...），一个是网上的版本，对于不如的格子更新路由数组记录的是k，另一种是《算法设计分析与设计》（陈惠南）中写的，此处记录值为path[k][j]，即经由k后到达j前的最后一步。下面我们来比较这两种对于该问题的优劣：
（1）记录k：这种路径回溯需要按照二叉树形式进行中序遍历，对于二叉树知识不好的可能有困难，且需要不断if...else...。
（2）记录最后路由路径：这种记录形式是线性的，方便获取最短路径。
因此我们选择第二种方式记录，线性方式回溯。
private static ArrayList FloydTraceBack(Station s1, Station s2) {
// if (s1.equals(s2)) System.err.println("FloydTraceBack-found:" + s1 + "==" + s2);
ArrayList floydPath = new ArrayList<>();
int idx1 = getStationIdx(TS_station, s1);
Station temp = s2;
do {
floydPath.add(temp);
} while (!s1.equals(temp = TS_path[idx1][getStationIdx(TS_station, temp)]));
floydPath.add(s1);
Collections.reverse(floydPath);
return floydPath;
}
对于动态规划的回溯
因为第一第三阶段的回溯是线路上的回溯，非常简单；中间的回溯已在上述步骤中完成。因此只需要将这几个步骤进行串联。具体如下：
private static ArrayList trace4Path() {
path.clear();
//从后往前依次记录每一站
//S3
Station s3 = dp_tags[dp_tags.length - 1];
path.add(s3);
//S3<-S2
Station s2 = dp_path[dp_tags.length - 1];
addList2Path(s3, s2);
//S2<-S1: 获得S1->S2的路线图，逆序并删去S2，依次记录路由站点
Station s1 = dp_path[getStationLastIdx(dp_tags, s2)];
if (s1.equals(s2))
s1=dp_path[getStationIdx(dp_tags,s2)];
//如果只需要转乘依次则S1==S2应当跳过S1直接S2<-S0
if (s1.isTS()) {
ArrayList tbArrays = FloydTraceBack(s1, s2);
Collections.reverse(tbArrays);
tbArrays.remove(0);
Station pre = s2;
for (Station cur : tbArrays) {
addList2Path(pre, cur);
pre = cur;
}
//S1<-S0
Station s0 = dp_path[0];
addList2Path(s1, s0);
} else {
Station s0 = dp_path[0];
addList2Path(s2, s0);
}
//运用Collections.reverse(path);进行逆序
Collections.reverse(path);
Utils.print1D(path.toArray(), 5, "path");
return path;
}
综上所述，整体流程如下：
public static double PathNavigation(Station S0, Station S3, double TS_Non) {
double d = A, d1 = A;
double[][] Dp_w;
System.out.println("------------start--------------" + TS_Non);
//generate all station information
if (!initStationInfo(S0, S3))
d1 = getLinearDistance(S0, S3, TS_Non) - (TS_STAY_MIN - NON_STAY_MIN) * (TS_Non - 1);
//generate all transferring stations' weight matrix
TS_cost = initTS_W_Matrix(TS_Non);
floyd();
//generate dp's weight matrix
Dp_w = initDp_W_Matrix(S0, S1, S2, S3, TS_Non);
d = dp(Dp_w);
//compare and the least cost between two methods
if (d < d1)
trace4Path();
else
System.out.println("直达最好：" + d1);
System.out.println("-------------end---------------");
return d;
}
该文件所有代码入下：
package core;
import utils.Utils;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class PathHelper {
public static final int A = 2097152;
public static final double TS_COST = 5;
public static final double TS_STAY_MIN = 3;
public static final double NON_STAY_MIN = 1;
public static final double V_KM_H = 60;
private static Station[] S1;
private static Station[] S2;
private static Station[] TS_station;
private static double[][] TS_cost;
private static Station[][] TS_path;
private static Station[] dp_tags;
private static double[] dp_cost;
private static Station[] dp_path;
private static ArrayList path;
public static double PathNavigation(Station S0, Station S3, double TS_Non) {
double d = A, d1 = A;
double[][] Dp_w;
System.out.println("------------start--------------" + TS_Non);
//generate all station information
if (!initStationInfo(S0, S3))
d1 = getLinearDistance(S0, S3, TS_Non) - (TS_STAY_MIN - NON_STAY_MIN) * (TS_Non - 1);
//generate all transferring stations' weight matrix
TS_cost = initTS_W_Matrix(TS_Non);
floyd();
//generate dp's weight matrix
Dp_w = initDp_W_Matrix(S0, S1, S2, S3, TS_Non);
d = dp(Dp_w);
//compare and the least cost between two methods
if (d < d1)
trace4Path();
else
System.out.println("直达最好：" + d1);
System.out.println("-------------end---------------");
return d;
}
private static boolean initStationInfo(Station S0, Station S3) {
path = new ArrayList<>();
S1 = Utils.list2Array(S0.getLinearTs());
S2 = Utils.list2Array(S3.getLinearTs());
TS_station = Utils.list2Array(Station.getAllTS());
if (S0.commonLineNum(S3) < A) {
path.add(S0);
addList2Path(S0, S3);
return false;
}
return true;
}
public static double dp(double[][] w) {
dp_cost = new double[w.length];
dp_path = new Station[w.length];
Arrays.fill(dp_cost, Integer.MAX_VALUE);
dp_path[0] = dp_tags[0];
dp_cost[0] = 0;
for (int j = 1; j < w.length; j++)
for (int i = j - 1; i >= 0; i--)
if (w[i][j] != A) {
double d = dp_cost[i] + w[i][j];
if (d < dp_cost[j]) {
dp_cost[j] = d;
dp_path[j] = dp_tags[i];
}
}
Utils.print1D(dp_tags, 5, "dp_tags");
Utils.print1D(dp_path, 5, "dp_path");
Utils.print1D(dp_cost, 8, "dp_cost");
return dp_cost[w.length - 1];
}
public static void floyd() {
TS_path = new Station[TS_station.length][TS_station.length];
//初始化路由矩阵
for (int i = 0; i < TS_station.length; i++)
for (int j = 0; j < TS_station.length; j++)
TS_path[i][j] = TS_cost[i][j] < A ? TS_station[i] : null;
//遍历floyd
for (int i = 0; i < TS_station.length; i++)
for (int j = 0; j < TS_station.length; j++)
for (int k = 0; k < TS_station.length; k++)
if (TS_cost[i][k] + TS_cost[k][j] < TS_cost[i][j]) {
TS_cost[i][j] = TS_cost[i][k] + TS_cost[k][j];
TS_path[i][j] = TS_path[k][j];
}
}
private static double[][] initTS_W_Matrix(double TS_Non) {
double[][] w = new double[TS_station.length][TS_station.length];
for (int i = 0; i < TS_station.length; i++) {
Arrays.fill(w[i], A);
for (int j = 0; j < TS_station.length; j++) {
if (i == j) w[i][j] = 0;
else
w[i][j] = getLinearDistance(TS_station[i], TS_station[j], TS_Non);
}
}
return w;
}
private static double getLinearDistance(Station s1, Station s2, double TS_Non) {
double speed = TS_Non == 2 ? V_KM_H / 60 * 1000 : 1;
int isPd = TS_Non == 2 ? 1 : 0;
//一般站点停靠时常
double stayTime = Math.abs(s1.linearDistance(s2, false)) * NON_STAY_MIN;
//换乘额外开销
double TsExtraCost = (TS_STAY_MIN - NON_STAY_MIN) * (TS_Non - 1);
//地铁运行时常
double runningTime = isPd * Math.abs(s1.linearDistance(s2, true)) / speed;
//路由中转站额外开销
double TsPassCost = isPd * s1.getInnerTsNum(s2) * (TS_COST - TS_STAY_MIN);
return stayTime + TsExtraCost + runningTime + TsPassCost;
}
private static double[][] initDp_W_Matrix(Station S0, Station[] S1, Station[] S2, Station S3, double TS_Non) {
double[][] w = new double[S1.length + S2.length + 2][S1.length + S2.length + 2];
dp_tags = new Station[S1.length + S2.length + 2];
//初始化dp_tags用于存储表头信息：
dp_tags[0] = S0;
for (int i = 0; i < S1.length; i++) dp_tags[1 + i] = S1[i];
for (int i = 0; i < S2.length; i++) dp_tags[1 + S1.length + i] = S2[i];
dp_tags[dp_tags.length - 1] = S3;
//w 初始化全为无穷大，表示不可达
for (double[] w_row : w)
Arrays.fill(w_row, A);
//w 对角线全为0
for (int i = 0; i < w.length; i++)
w[i][i] = 0;
//处理S0->S1的权值表
//换乘比只计算起点，不计算终点，TS已在生成Matrix完成
for (int i = 0; i < S1.length; i++) {
w[0][1 + i] = getLinearDistance(S0, S1[i], TS_Non);
}
//处理S1->S2的权值表
for (int i = 0; i < S1.length; i++) {
for (int j = 0; j < S2.length; j++) {
int idx1 = getStationIdx(TS_station, S1[i]);
int idx2 = getStationIdx(TS_station, S2[j]);
//只处理w的上三角
w[1 + i][1 + S1.length + j] = TS_cost[idx1][idx2];
}
}
//处理S2->S3的权值表
for (int i = 0; i < S2.length; i++) {
//去掉尾端多记录的换乘比
w[1 + S1.length + i][w.length - 1] = getLinearDistance(S3, S2[i], TS_Non) - (TS_Non - 1) * (TS_STAY_MIN - NON_STAY_MIN);
}
return w;
}
private static int getStationIdx(Station[] stations, Station key) {
for (int i = 0; i < stations.length; i++)
if (key.equals(stations[i])) return i;
return -1;
}
private static int getStationLastIdx(Station[] stations, Station key) {
for (int i = stations.length - 1; i >= 0; i--)
if (key.equals(stations[i])) return i;
return -1;
}
private static ArrayList trace4Path() {
path.clear();
//从后往前依次记录每一站
//S3
Station s3 = dp_tags[dp_tags.length - 1];
path.add(s3);
//S3<-S2
Station s2 = dp_path[dp_tags.length - 1];
addList2Path(s3, s2);
//S2<-S1: 获得S1->S2的路线图，逆序并删去S2，依次记录路由站点
Station s1 = dp_path[getStationLastIdx(dp_tags, s2)];
if (s1.equals(s2))
s1=dp_path[getStationIdx(dp_tags,s2)];
//如果只需要转乘依次则S1==S2应当跳过S1直接S2<-S0
if (s1.isTS()) {
ArrayList tbArrays = FloydTraceBack(s1, s2);
Collections.reverse(tbArrays);
tbArrays.remove(0);
Station pre = s2;
for (Station cur : tbArrays) {
addList2Path(pre, cur);
pre = cur;
}
//S1<-S0
Station s0 = dp_path[0];
addList2Path(s1, s0);
} else {
Station s0 = dp_path[0];
addList2Path(s2, s0);
}
//运用Collections.reverse(path);进行逆序
Collections.reverse(path);
Utils.print1D(path.toArray(), 5, "path");
return path;
}
private static ArrayList addList2Path(Station sta, Station end) {
Station[] stations = sta.linearPathTo(end);
// if (stations==null) return path;
for (int i = 1; i < stations.length; i++)
path.add(stations[i]);
return path;
}
private static ArrayList FloydTraceBack(Station s1, Station s2) {
// if (s1.equals(s2)) System.err.println("FloydTraceBack-found:" + s1 + "==" + s2);
ArrayList floydPath = new ArrayList<>();
int idx1 = getStationIdx(TS_station, s1);
Station temp = s2;
do {
floydPath.add(temp);
} while (!s1.equals(temp = TS_path[idx1][getStationIdx(TS_station, temp)]));
floydPath.add(s1);
Collections.reverse(floydPath);
return floydPath;
}
public static ArrayList getPath() {
return path;
}
}
好了，以上就是这一小节讲解的如何将最短路径算法的实现，完成三种需求的数据读取。感谢友友们一键三连哦，下一节我们接着说简单GUI图形化界面制作。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）