python - 修改 Dijkstra 算法以获得最少的变化

Question

我正在使用我在网上找到的用 Python 编写的 Dijkstra 算法版本，它运行良好。但是因为这是公交路线，换10次可能是最短的路线，但可能不是最快的，也绝对不是最容易的。我需要以某种方式修改它以返回更改次数最少的路径，老实说，无论距离如何(显然，如果 2 条路径的更改次数相同，则选择最短的路径)。我目前的代码如下:

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) 从起始顶点运行广度优先搜索。它会找到变化最少的路径，但不是其中最短的。假设在运行广度优先搜索后，dist[i] 是起点和第 i 个顶点之间的距离。

2) 现在可以在修改后的图上运行 Djikstra 算法(仅添加初始图中满足此条件的那些边:dist[from] + 1 == dist[to])。此图中的最短路径就是您要查找的路径。

P.S 如果你不想使用广度优先搜索，你可以在使所有边的权重都等于1之后使用Djikstra算法。