这是我数据结构课设的题目,我觉得我在这道题目里的做法是比较经典,比较有启发意义的,对以后图的优化问题提供了一个比较好的思路。下面是我在课上做的slides,可以点击此处下载。

ds_slides

题意

问题描述

最短路径问题是图论中的一个经典问题,其中的Dijkstra算法一直被认为是图论中的好算法,但有的时候需要适当的调整Dijkstra算法才能完成多种不同的优化路径的査询。

对于某城市的公交线路,乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。

设该城市的公交线路的输入格式为:

线路编号: 起始站名(该站坐标); 经过的站点1名(该站坐标); 经过的站点2名(该站坐标); 经过的站点n名(该站坐标); 终点站名(该站坐标)。该线路的乘坐价钱。该线路平均经过多少时间来一辆。车速。

例如:63: A(32,45); B(76,45); C(76,90); ...; N(100,100)。1元。5分钟。1/每分钟。假定线路的乘坐价钱与乘坐站数无关,假定不考虑公交线路在路上的交通堵塞。对这样的公交线路,需要在其上进行的优化路径查询包括任何两个站点之间最便宜的路径任何两个站点之间最省时间的路径等等

基本要求

  1. 根据上述公交线路的输入格式,定义并建立合适的图模型。
  2. 针对上述公交线路,能查询获得任何两个站点之间最便宜的路径,即输入站名S, T后,可以输出从S到T的最便宜的路径,输出格式为:线路x: 站名S, ..., 站名M1; 换乘线路x: 站名M1, ..., 站名M2; 换乘线路x站名MK, ..., 站名T。共花费x元。
  3. 针对上述公交线路,能查询获得任何两个站点之间最省时间的路径(不考虑在中间站等下一辆线路的等待时间),即输入站名S, T后,可以输出从S到T的考虑在中间站等下辆线路的等待时间的最省时间的路径,输出格式为:线路x: 站名S, ..., 站名M1; 换乘线路x: 站名M1, ...,站名M2; 换乘线路x: 站名MK, ..., 站名T。共花费x时间。
  4. 针对上述公交线路,能查询获得任何两个站点之间最省时间的路径(要考虑在中间站等下一辆线路的等待时间),即输入站名S, T后,可以输出从S到T的考虑在中间站等下辆线路的等待时间的最省时间的路径,输出格式为:线路x: 站名S,..., 站名M1; 换乘线路x: 站名M1, ..., 站名M2; 换乘线路x: 站名MK, ..., 站名T。共花费x时间。

实现提示

需深入考虑,应根据不同的应用目标,即不同的优化査询来建立合适的图模型。

算法思路

本篇博客均以下面的图进行举例,这张图是我从青岛市的一些公交线路简化而来的。我们要从“山东大学公交换乘站”到“青岛大学”,目标是“最便宜”/”最省时间”。
首先我们需要确认一点,不能在原图上直接做最短路。举个例子,假设我现在要选择最便宜的路线,我在“汽车东站”发现那条绿色的线路需要2元,红色的线路需要1元,而我要选择最便宜的,就简单的把绿色的线路丢弃而选择红色的线路(Dijkstra算法就是这么做的),然后我在这个站点又需要上绿色的线路,总的价钱是3元;但如果我从一开始就直接选择绿色的线路的话,只需要2元就够了。从这一点就可以看出此问题与最短路问题的不同,\(s\)到\(t\)经过点\(i\)的最短路为\(dist(s, i) + dist(i, t)\),但该公式在本题中不满足。

那么最核心解决方法是:记录通过每一条进入该点的线路的最短路。即在“汽车东站”需要分别记录绿色和红色的线路到达“汽车东站”的最短路。

但当时的我的想法有些不一样,想通过重新建图来模拟在不同线路间换乘这一过程:首先把不同线路的相同站点视为不同的站点,即把不同的线路拆分开。如下图所示:这样缺少了“在某站下车换乘另一条线路”这个条件,因此我们使用站内边进行连接,表示换乘关系:

但这样又会产生一个问题,如果有\(n\)条线路同时经过一个站点,那么我们就需要添加\(n(n-1)/2\)条站内边,其实还是蛮大的一个开销。我们可以通过建立一个虚拟节点来规避这种开销,把边数从\(n(n-1)/2\)降到\(2n\):

至于每条边的边权如何确定,如果是“最便宜”路线的话,在每条线路上的边的边权是0,下车的边(连接到虚拟节点上的边)的边权也是0,只有在上车的边(从虚拟节点连接出去的边)的边权是该线路的费用;如果是“最省时间”路线的话,在每条线路上的边的边权是两站点间距离/该线路车速,下车的边的边权是0,上车的边的边权是该线路的平均等待时间。

状态转移视角

之前一直是图的视角,考虑如何重新建图,每条边应该如何连接……现在我们用状态转移的视角重新思考下这个问题,考虑数学上较为形式化的表达,为我们之前算法的合理性和正确性提供证明,并对算法运行的时空复杂度进行分析。

设\(p_{i,j}\)表示第\(i\)条线路的第\(j\)个站点,\(s_{i,j}\)表示在第\(i\)条线路的车上,此时位于第\(j\)个站点的状态,\(f(s_{i, j})\)表示从起始站点\(S\)出发,到达\(st_{i, j}\)的最小代价。

\[\begin{align*}f(st_{i,j}) = min\{&f(st_{i,j – 1}) + cost(st_{i,j – 1}, st_{i,j}) | j > 1,\\ &f(st_{k,l}) + cost(st_{k, l}, st_{i, j}) | p_{i,j} = p_{k,l}\wedge (i, j) \neq (k, l)\}\end{align*}\]

显然这个不能用动态规划解决,因为不满足无后效性,但我们回想下最短路的状态转移方程(思想来自Bellman-Ford算法):

\[d(i) = min\{d(j) + cost(i, j) | (i, j) \in E\}\]

我们发现他们形式一致,而且没有负权,因此可以使用Dijkstra算法进行求解。但是这样转移复杂度较高,我们需要找到一种方法方便地找到这样的\(st_{k, l}\),因此我们提出了一种与之前的虚拟节点相似的一种状态,即设\(st_{0,j}(1 \leq j \leq m)\)表示当前在$j$站点且没有上车的状态。那么,

当\(i > 0\)时,

\[\begin{align*}f(st_{i,j}) = min\{&f(st_{i,j – 1}) + cost(st_{i,j – 1}, st_{i,j}) | j > 1,\\ &f(st_{0,p_{i, j}}) + cost(st_{0,p_{i, j}}, st_{i, j}) \}\end{align*}\]

当\(i = 0\)时,

\[\begin{align*}f(st_{0,j}) = min\{f(st_{k,l}) | j = p_{k,l} \}\end{align*}\]

算法实现




时空复杂度分析

Dijkstra + 二叉堆时间复杂度为\(O(|E|\log |V|)\),Dijkstra + Fibonacci堆时间复杂度为\(O(|E| + |V|\log |V|)\)。设总共\(n\)条路径,路径\(i\)的站点数为\(r_i\),\(m\)个站点,经过站点\(i\)的路径条数为\(s_i\)(一条线路经过相同站点多次算作多条路径),显然有\(N = \sum_{i = 1}^{n} r_i = \sum_{i = 1}^{m} s_i\),输入规模为\(N\),则

\[\begin{align*}|E| =& \sum_{i = 1}^{n}(r_i – 1) + \sum_{i = 1}^{m}2 s_i\\=& 3 \sum_{i = 1}^{n} r_i – n\\=& 3N – n\end{align*}\]

\[\begin{align*}|V| =& \sum_{i = 1}^{n}r_i + m\\=& N + m\end{align*}\]

则时间复杂度为\(O((3N – n)\log (N + m)) = O(N\log N)\),空间复杂度为\(O(N)\)。

可能的优化

显然在计算最小费用时图过于稀疏了,因为线路内的边,下车的边的权重都为0,所以可能可以为线路维护一个类似集合的数据结构,可能能得到更高的时间效率。