所谓联程算法，就是两个无法直达的点，可以通过中转到达。在现在的飞行，高铁中很常见，我们的产品也遇到了类似的问题。
不管是用targin算法还是Dijkstra算法都不能很好的完成我的目的，于是我用了可达矩阵的一种矩阵相乘的思路。
思路：采用矩阵相乘的方式进行联程计算、换乘次数就是相乘的次数。
步骤：
- Step1:构造可达矩阵
- Step2:根据换乘次数进行矩阵相乘
- Step3:构造返回结果
- A11->A12->A13
- A21->A12->A23->A24
- A31->A23->A33->A34
* Step1:构造可达矩阵
其中A12和A23是换乘站。A11 A13为route1的起点和重点站，A21 A24是route2的起点和终点站。A31和A34是Route3的起点终点站。如果两个站点之间可达，即为1，否则即为0，于是构造可达矩阵为一个8 * 8的矩阵如下：
| |
A11 |
A12 |
A13 |
A21 |
A23 |
A24 |
A31 |
A34 |
| A11 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
| A12 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
| A13 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
| A21 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
| A23 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
| A24 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
| A31 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
| A34 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
解释：
第一行、A11->A11 可达为1 A11->A12 可达为1 A12->A13可达为1 其余均不可达，为0。
第二行。A12->A12 A12->A13 A12->A23 A12->A24可达为1其余皆为0。
其余行相同。
* Step2:根据换乘次数进行矩阵相乘
矩阵的平方结果（只能换成一次的结果）：
| |
A11 |
A12 |
A13 |
A21 |
A23 |
A24 |
A31 |
A34 |
| A11 |
1 |
2 |
3 |
0 |
1 |
1 |
0 |
0 |
| A12 |
0 |
1 |
2 |
0 |
2 |
3 |
0 |
1 |
| A13 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
| A21 |
0 |
2 |
1 |
1 |
3 |
4 |
0 |
1 |
| A23 |
0 |
0 |
0 |
0 |
1 |
2 |
0 |
2 |
| A24 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
| A31 |
0 |
0 |
0 |
0 |
2 |
1 |
1 |
3 |
| A34 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
第一行解读，从A11可以到达的站点为A12 A13 A24。其中A24为之前不为1，相乘之后为1的，也就是说是一个联程可达的站点。
标红色的地方均为1次换乘可达的联程点：
A11->A23 A11->A24
A12->A34
A21->A13 A21->A34
A31->A24
A12和A23为换乘点，所以不作为最终统计。最终结果为
A11->A24 A21->A13 A21->A34 A31->A24
将这个结果再乘以第一个矩阵结果（换乘两次的结果）：
| |
A11 |
A12 |
A13 |
A21 |
A23 |
A24 |
A31 |
A34 |
| A11 |
1 |
3 |
6 |
0 |
3 |
4 |
0 |
1 |
| A12 |
0 |
1 |
3 |
0 |
3 |
6 |
0 |
3 |
| A13 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
| A21 |
0 |
3 |
3 |
1 |
6 |
10 |
0 |
4 |
| A23 |
0 |
0 |
0 |
0 |
1 |
3 |
0 |
3 |
| A24 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
| A31 |
0 |
0 |
0 |
0 |
3 |
3 |
1 |
6 |
| A34 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
换乘两次新出现的为1的为红色标注的，即为 A11->A34
如何返回最终结果？以A11->A34为例
A11与A34之间的换乘线路只要相较于之前的矩阵有变化，即为通过的换乘线路。
最困难的地方在于构造第一个可达矩阵，这里需要考虑换乘点的间隔时间是是否可达的关键，这里不需要考虑环线。因为这个矩阵相同的站点只保留一个。
矩阵中每一个Slot的类可以记录站点的信息，这样可以重写矩阵相乘的方法把线路可以直接得到就像A11->A34 就是A11->A12->A23->A34.
解决问题的难以程度，关键看建模的好坏。
一个联程算法的描述
原文：https://www.cnblogs.com/weggi/p/11956657.html
