<p>毫无疑问,图中会有大量的最短路径。因此在满足时间复杂度的情况下,很难生成所有的最短路径。但是我可以给你一个简单的方法,可以得到你想要的最短路径。</p>
<h2>算法</h2>
<ol>
<li>从起点运行Dijkstra算法,得到disS[i]列表(最短距离
在起点和点i之间)。然后从终点运行Dijkstra算法,得到disT[i]列表(终点到点i的最短距离)</li>
<li>创建新图形:对于原始图形中的边,如果
disS[a]+disT[b]+w(a,b)==disS[结束点],我们在新图中添加一条边。很明显,新的图是一个DAG(有向无环图),有一个sink(起点)和一个target(终点)。从sink到目标的任何路径都是原始图中的最短路径。</li>
<li>您可以在新图表中运行DFS。将路径信息保存在
递归和回溯,当你到达目标时,保存
信息将是一条最短的路径。什么时候算法结束都取决于你。</li>
</ol>
<h2>伪代码:</h2>
<pre><code>def find_one_shortest_path(graph, now, target, path_info):
if now == target:
print path_info
return
for each neighbor_point of graph[now]:
path_info.append(neighbor_point)
find_one_shortest_path(graph, neighbor_point, target, path_info) #recursion
path_info.pop(-1) #backtracking
def all_shortest_paths(graph, starting_point, ending_point):
disS = [] # shortest path from S
disT = [] # shortest path from T
new_graph = []
disS = Dijkstra(graph, starting_point)
disT = Dijkstra(graph, endinng_point)
for each edge<a, b> in graph:
if disS[a] + w<a, b> + disT[b] == disS[ending_point]:
new_graph.add(<a, b>)
find_one_shortest_path(new_graph, starting_point, ending_point, [])
</code></pre>