基于Dijkstra算法：寻找源点到多终点的边权递减型所有最短路径

嘿，这个问题涉及到Dijkstra算法的两个实用扩展点：找出所有可行的最短路径（而非单条最优解），同时保证这些路径的边权重按降序排列。我来一步步拆解实现思路：

1. 基础改造：让Dijkstra记录所有最短路径的前驱 #

标准Dijkstra只会为每个节点记录一个前驱（找到第一条最短路径时的节点），但要收集所有最短路径，我们需要给每个节点维护一个前驱节点集合，而非单个前驱。具体调整如下：

• 初始化时，源节点s的距离dist[s] = 0，其余节点dist[v] = ∞。
• 维护字典predecessors，其中predecessors[v]存储所有满足dist[u] + weight(u,v) = dist[v]的节点u——这些u都是能通过最短路径到达v的前驱节点。
• 松弛操作时：
  • 如果dist[u] + weight(u,v) < dist[v]：更新dist[v]为新的最短距离，清空predecessors[v]并加入当前u。
  • 如果dist[u] + weight(u,v) == dist[v]：直接将u追加到predecessors[v]中（这代表找到了另一条到达v的最短路径）。

这一步能帮我们收集到所有可能的最短路径前驱，为后续生成完整路径打基础。

2. 筛选符合边权重降序的最短路径 #

现在我们有了所有最短路径的前驱，但需要从中筛选出边权重按降序排列的路径。核心规则是：一条从s到t的最短路径，其边的权重必须满足w1 >= w2 >= ... >= wk（w1是源节点出发的第一条边权重，wk是到达目标节点的最后一条边权重）。

实现筛选可以结合回溯法，在生成路径的同时检查边的顺序：

• 从目标节点t开始回溯，递归遍历每个前驱u：
  • 如果当前节点是源节点s，直接记录路径[s]。
  • 否则，先获取从s到u的所有符合降序要求的最短路径，再将边u->t的权重与该路径的最后一条边权重比较：如果weight(u,t) <= 路径最后一条边的权重，就将u->t追加到路径末尾，形成新的符合要求的路径。
• 最后将回溯得到的路径反转，就能得到从s到t的、边权重降序排列的最短路径。

举个例子：假设s->a权重5，a->t权重3；s->b权重4，b->t权重4。两条路径总长度都是8，第一条边序列[5,3]是降序，第二条[4,4]也是降序，都会被保留；如果有一条s->c权重3，c->t权重5，总长度同样是8，但边序列[3,5]是升序，就会被过滤掉。

3. 批量处理多个目标节点 #

对于多个目标节点，只需要对每个目标节点重复步骤2即可。你可以把所有目标节点放在一个列表里，遍历列表逐个生成符合要求的最短路径，最后整理结果即可。

4. 构建符合要求的最短路径树 #

如果需要构建对应的最短路径树，可以基于筛选后的路径生成：

• 树的节点就是原图中的节点，边只保留那些出现在符合要求的最短路径中的边。
• 为了保证树的结构（每个节点除源节点外只有一个父节点），如果一个节点有多个符合条件的前驱，你可以选择边权重最大的那个前驱（最大化路径的降序特性），或者根据需求选择任意一个符合条件的前驱。

代码思路示例（伪代码） #

import heapq

def modified_dijkstra(graph, source):
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    predecessors = {node: [] for node in graph}
    priority_queue = [(0, source)]
    
    while priority_queue:
        current_dist, u = heapq.heappop(priority_queue)
        if current_dist > dist[u]:
            continue
        for v, weight in graph[u].items():
            if dist[v] > dist[u] + weight:
                dist[v] = dist[u] + weight
                predecessors[v] = [u]
                heapq.heappush(priority_queue, (dist[v], v))
            elif dist[v] == dist[u] + weight:
                if u not in predecessors[v]:
                    predecessors[v].append(u)
    return dist, predecessors

def generate_descending_paths(predecessors, graph, source, target):
    paths = []
    def backtrack(node, current_path, last_weight):
        if node == source:
            # 反转路径得到从源到目标的顺序
            paths.append([source] + [n for n, _ in reversed(current_path)])
            return
        for u in predecessors[node]:
            edge_weight = graph[u][node]
            # 检查降序：第一条边无前置权重，直接通过；后续边需小于等于上一条边的权重
            if last_weight is None or edge_weight <= last_weight:
                backtrack(u, current_path + [(node, edge_weight)], edge_weight)
    backtrack(target, [], None)
    return paths

# 使用示例
graph = {
    's': {'a':5, 'b':4, 'c':3},
    'a': {'t':3},
    'b': {'t':4},
    'c': {'t':5},
    't': {}
}
dist, predecessors = modified_dijkstra(graph, 's')
targets = ['t']
for target in targets:
    valid_paths = generate_descending_paths(predecessors, graph, 's', target)
    print(f"从s到{target}的符合要求的最短路径：{valid_paths}")

这段代码会输出[['s', 'a', 't'], ['s', 'b', 't']]，而s->c->t这条路径因为边权重升序被过滤了。

注意事项 #

• 如果图中有环，但因为是最短路径，环的总权重必然为正（否则最短路径不存在），所以回溯时不会出现无限循环。
• 如果多个目标节点有重叠的路径段，可以缓存已经生成的路径段，避免重复计算，提升效率。

内容的提问来源于stack exchange，提问作者Annie