被裁老程序员再就业计划之我可以用Dijkstra算法在回龙观送外卖

2023-02-12 11:24:00

疫情原因，公司干脆利落地把我们业务组给裁啦，我也光荣地成为了一个下岗待业的老程序员。

开发工作不好找啊，毕竟都要35岁以下的，所以我寻思再就业可以换个方向，比如说送外卖，再怎么说X团、X了么也是大厂嘛~

既然下定决心，第一步就是要武装头脑，拿起理论的武器，送外卖第一要务是什么？快！！天下武功，唯快不破。速度速度速度，重要的事情说三遍。

如何快速抵达商家，再快速将饭菜送到顾客手中，少跑路是关键——这就是最短路径问题，下面我就描述一下，我是如何使用Dijkstra算法结合回龙观的地图来计算最短路径的。

选回龙观的原因：1、回龙观的道路情况很好，基本上是横平竖直；2、我家就在这，送外卖在家附近送，路熟。

回龙观的地图如上，因为是做实验，就选取了部分区域：北起回南北路，南至同成街；东起G6辅路，西至文化东路。

之前我的两篇描述最短路径算法的文章中，使用的图都是类似：

如果用在地图上，就有些不合适，因为不太好体现真实情况，如下图：

在示意图中，两点之间只会有一条边A，但现实中，两地的路线有B、C两条，所以为了让示意图更贴合显示，就有了变种图：

每一个方块代表一个顶点，两个相邻顶点的边权重视为1.

如上图，其中蓝色数字的方块代表可通过的路，红色英文的方块代表不可通行，其顶点边权组合应如下：

1-2-1，1-16-1

2-1-1，2-3-1

3-2-1，3-4-1，3-17-1

4-3-1，4-5-1

5-4-1，5-6-1

...... ......

18-17-1，18-19-1，18-20-1，18-21-1

假如以北店嘉园北区东门为起点，即19，以龙回苑西门为终点，即5.

可得最短路线为19-18-21-7-6-5或19-18-17-3-4-5，再结合实际道路情况，例如拥堵程度、红绿灯、单行路等，可得出相对较短的路线。

假设龙禧二街常年堵车，边权设为2，则较短路径应为第二条。

我使用地图的测距工具得到了以下不怎么精确的距离：

以路口为点，两点之间的距离如上图，单位公里。

我假设每一个方块都代表100*100米，那么示意图如下：

不要问为什么是圆而不是说好的方块，因为圆比方块好画~~~

也请忽视圆的大小不一，单位固定都是100*100米。

接着我们上代码。

首先我们必须构建顶点的边权数据，类似1-45-1，1-74-1这种。

在这里我采用了Guava里的HashBasedTable结构，即Key1-Key2:Value。


Table<Integer, Integer, Integer> ppw = HashBasedTable.create();
ppw.put(1, 45, 1);
ppw.put(1, 74, 1);
ppw.put(45, 1, 1);
ppw.put(74, 1, 1);

在本图里，共有296个顶点，相关边更多，纯手工录入会崩溃的，所以我写了程序，根据输入的顶点范围生成相应的代码。即便这样也是很累人的。

接着实现Dijkstra算法。伪代码如下，入参有两个：起点，终点，


public void getShortestPath(Integer start, Integer end){
 1、构建到某一顶点最短路径的起点Map——parentMap
 2、构建已处理最短路径顶点Map——s；构建待处理最短路径顶点Map——w
 3、构建(顶点A-顶点B:边权)的Table——ppw
 4、遍历所有顶点{
  4.1将w转为优先队列，并取出最小值的顶点，将其从w挪入s，并以此为顶点（设为Key1）计算其相邻顶点的权重。
  4.2如果取出的最小值顶点就是终点，且最小值不是无穷大（在程序中用Integer.MAX_VALUE代替），说明已经计算到终点，不需要计算后面的点，直接跳出循环。
  4.3内循环遍历所有顶点（设为Key2），根据Key1-Key2从ppw中取出权重。
  4.4如果ppw取出为null，说明两顶点间无路径。
  4.5根据Key1、Key2的值、边权对Key2进行松弛操作。
 }
}

至此，核心代码已经完成，后续还有输入骑手、商家、顾客，调用核心代码，并输出路径的方法等，在此不再赘述。

以下为测试结果。

假设骑手在回龙观西大街与育知东路的交叉口（即24），商家在北京华联同成街店（即177），顾客在天露园二区北门（即89），计算的结果如下：

以商家到顾客路线为例，地图给出的路径如图：

程序给出的路径：

基本还算一致。

当然这只是一个很简陋的程序，有许多实际问题没有考虑，比如出行方式、拥堵、红绿灯、单行道、禁行路段、立体交通等。

例如点26，同成街与育知东路交叉点，这其实是个桥，如果从175到236，开车的话是不可能走175-26-236路线的，必须绕一圈。

这篇文章其实也只是记录一下个人将理论与实际相结合的学习过程，疏漏错误在所难免。

码农公寓

相关文章