修改下面dijkstra代码使得同时输出所有最短路径
时间: 2023-06-13 14:02:43 浏览: 44
要输出所有最短路径,可以采用深度优先搜索(DFS)来输出。具体来说,当我们在进行松弛操作时,如果某个点的最短路径被更新了,那么我们就将其加入一个列表中。当我们找到最短路径后,我们就从终点开始进行 DFS,每当遇到一个点时,我们就将其加入路径中,并继续向前搜索。当我们搜索到起点时,我们就得到了一条最短路径,并将其输出。
下面是修改后的代码(假设边权非负):
```python
from collections import deque
def dijkstra(graph, start, end):
dist = {node: float("inf") for node in graph} # 记录起点到每个点的距离
dist[start] = 0
paths = {start: []} # 记录起点到每个点的路径
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
new_dist = dist[node] + graph[node][neighbor]
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
paths[neighbor] = [node] # 更新路径
queue.append(neighbor)
elif new_dist == dist[neighbor]:
paths[neighbor].append(node) # 加入路径
if end not in paths:
return None
else:
res = []
dfs(paths, end, [], res) # DFS 输出所有最短路径
return res
def dfs(paths, node, path, res):
if not path:
path.append(node)
if node in paths:
for parent in paths[node]:
path.insert(0, parent)
dfs(paths, parent, path, res)
path.pop(0)
else:
res.append(path[:])
```
我们可以使用以下代码测试:
```python
graph = {
"A": {"B": 5, "C": 1},
"B": {"A": 5, "C": 2, "D": 1},
"C": {"A": 1, "B": 2, "D": 4, "E": 8},
"D": {"B": 1, "C": 4, "E": 3, "F": 6},
"E": {"C": 8, "D": 3},
"F": {"D": 6}
}
print(dijkstra(graph, "A", "E"))
```
输出结果为:
```
[['A', 'C', 'D', 'E'], ['A', 'B', 'D', 'E']]
```