修改迪杰斯特拉算法以最小变动

Question

我在网上找到了一种用Python写的Dijkstra算法，效果很好。不过因为这是用来计算公交路线的，换乘10次可能是最短的路线，但不一定是最快的，肯定也不是最简单的。我需要对这个算法做些修改，让它返回换乘次数最少的路线，实际上距离并不是最重要的（当然，如果有两条路线换乘次数相同，就选择距离最短的那条）。我现在的代码如下：

from priodict import priorityDictionary

def Dijkstra(stops,start,end=None):
    D = {}  # dictionary of final distances
    P = {}  # dictionary of predecessors
    Q = priorityDictionary()   # est.dist. of non-final vert.
    Q[start] = 0

    for v in Q:
        D[v] = Q[v]
        print v
        if v == end: break

        for w in stops[v]:
            vwLength = D[v] + stops[v][w]
            if w in D:
                if vwLength < D[w]:
                    raise ValueError, "Dijkstra: found better path to already-final vertex"
            elif w not in Q or vwLength < Q[w]:
                Q[w] = vwLength
                P[w] = v
    return (D,P)

def shortestPath(stops,start,end):
    D,P = Dijkstra(stops,start,end)
    Path = []
    while 1:
        Path.append(end)
        if end == start: break
        end = P[end]
    Path.reverse()
    return Path

stops = MASSIVE DICTIONARY WITH VALUES (7800 lines)
print shortestPath(stops,'Airport-2001','Comrie-106')

我得坦白，我不是数学高手，所以尽管我做了很多研究，还是不太理解这个算法。

我尝试修改了一些地方，但结果离我想要的还差得远。

有没有人能帮帮我？谢谢！

Answer 1

我会建议在实际费用上加一个偏移量，如果你需要改变线路的话。比如说，如果你的边权重代表了两个站之间所需的时间，我会在搜索过程中加上线路1和线路2在站点X之间的平均等待时间（比如说0.5乘以最大等待时间）。当然，这只是一个启发式的解决方案。如果你的时刻表是已知的，你可以计算出一个“精确”的解决方案，或者至少是一个符合模型的解决方案，因为实际上你不能假设每辆公交车总是准时到达。

Answer 2

解决方案很简单：与其把距离当作权重，不如给每个停靠点都设定一个权重为1。这样，Dijkstra算法就能帮你最小化换乘次数，正如你所要求的那样（总的路径权重就是乘坐的次数，也就是换乘次数加1）。如果你想用距离来打破平局，可以使用类似下面的方式：

 vwLength = D[v] + 1+ alpha*stops[v][w]

其中alpha<<1，比如说alpha=0.0001。

实际上，我觉得你的方法有点夸张。即使有两趟航班是最便宜的，你也不想从波士顿飞到多伦多还要绕道巴黎。我会调整alpha的值，以便更好地估算总的旅行时间，这才是最重要的。

Answer 3

这里有一个可能的解决方案：

1) 从起始点开始，进行广度优先搜索。这种方法会找到变化次数最少的路径，但不一定是最短的路径。假设在运行完广度优先搜索后，dist[i] 表示从起始点到第 i 个点的距离。

2) 接下来，可以在修改过的图上运行 Dijkstra 算法（只添加那些满足这个条件的边：dist[from] + 1 == dist[to]）。在这个图中找到的最短路径就是你想要的。

附注：如果你不想使用广度优先搜索，可以在将所有边的权重都设为 1 后，直接使用 Dijkstra 算法。