无向图两顶点间最短路径求解：如何从生成的所有路径中筛选最短路径？

你已经有了生成所有路径的基础Prolog代码，接下来要筛选出最短路径，这里提供两种实用方案——一种是先收集所有路径再筛选（直观但适合小规模图），另一种是搜索时动态剪枝（效率更高，适合大图）。

方案一：收集所有路径后筛选最短 #

首先我们可以用findall把所有路径和对应的长度收集起来，再通过排序找到最短的那条。

步骤1：收集所有路径 #

先定义一个谓词来获取所有(路径长度, 路径)对：

all_paths(X, Y, Paths) :-
    findall((Length, Path), path(X, Y, Path, Length), Paths).

步骤2：筛选最短路径 #

利用Prolog的排序特性（默认按元组第一个元素升序），取排序后的第一个元素就是最短路径：

shortest_path(X, Y, ShortestPath, MinLength) :-
    all_paths(X, Y, Paths),
    sort(Paths, SortedPaths),
    SortedPaths = [(MinLength, ShortestPath)|_].

如果需要获取所有长度相同的最短路径，可以调整为：

all_shortest_paths(X, Y, ShortestPaths, MinLength) :-
    all_paths(X, Y, Paths),
    Paths \= [],  % 确保存在路径
    Paths = [(MinLength, _)|_],
    findall(Path, member((MinLength, Path), Paths), ShortestPaths).

方案二：搜索时动态剪枝（高效版） #

如果图比较大，生成所有路径会非常耗时，这时可以用分支限界法：在搜索过程中记录当前找到的最短长度，一旦当前路径长度超过这个值，就停止这条分支的搜索，避免无效计算。

先修复原始路径谓词（避免循环） #

首先要给你的path谓词加上已访问节点的记录，防止图中有环时无限递归：

% 内部谓词，带已访问节点列表
path(X, Y, [X,Y], L, Visited) :-
    \+ member(Y, Visited),
    edge(X, Y, L).
path(X, Y, [X|W], L, Visited) :-
    \+ member(X, Visited),
    edge(X, Z, L1),
    path(Z, Y, W, L2, [X|Visited]),
    L is L1 + L2.

% 对外接口，初始化已访问列表为空
path(X, Y, Path, L) :-
    path(X, Y, Path, L, []).

实现动态剪枝的最短路径搜索 #

% 初始调用：先找到第一条路径作为初始最短值
shortest_path_opt(X, Y, ShortestPath, MinLength) :-
    path(X, Y, FirstPath, FirstLength),
    shortest_path_opt(X, Y, FirstPath, FirstLength, ShortestPath, MinLength).

% 递归寻找更短的路径，更新当前最优解
shortest_path_opt(X, Y, CurrentBestPath, CurrentMinLength, ShortestPath, MinLength) :-
    path(X, Y, NewPath, NewLength),
    NewLength < CurrentMinLength,
    shortest_path_opt(X, Y, NewPath, NewLength, ShortestPath, MinLength).

% 终止条件：没有找到更短的路径，返回当前最优
shortest_path_opt(_, _, ShortestPath, MinLength, ShortestPath, MinLength).

这个版本会在回溯过程中不断更新最短路径，一旦没有更短的路径就停止，效率比第一种方案高很多。

注意事项 #

• 如果两个顶点之间没有路径，所有谓词都会失败，你可以根据需求添加失败后的处理逻辑。
• 原始的path谓词如果不处理环，会生成无限长的路径，导致findall陷入死循环，所以一定要加上已访问节点的判断。

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