打印有向图中的最短路径

Question

我有一个没有权重的有向循环图。我想找到 A 和 B 之间的最短路径（即跳数最少的路径）。

这是我目前得到的代码：

path(A,B) :- walk(A,B,[]).

walk(A,B,V) :- edge(A,X), not(member(X,V)), (B=X); walk(X,B,[A|V]).

edge(a, b).
edge(b, c).
edge(a, d).
edge(c, a).

此代码为找到的每条路线打印一次。我怎样才能打印路径？我需要做什么才能找到跳数最少的路径？

Answer 1

要生成路径，您需要添加一个参数来跟踪它；例如：

path(A,B,P) :- walk(A,B,[],P).
walk(A,B,V,[A,B]) :- edge(A,X), not(member(X,V)), (B=X).

（我将把递归案例留作练习。）

要找到最短路径，您可以找到所有路径 (findall) 并选择最短路径。

Answer 2

一旦达到终止条件，您需要将一个额外的参数与您在 V 中积累的内容统一起来：

path(A,B,P) :- walk(A,B,[],P).

walk(B,B,V,P) :- reverse(V,P).
walk(A,B,V,P) :- dif(A,B), edge(A,X), maplist(dif(X),V), walk(X,B,[A|V],P).

一旦 A 和 B 相同，就意味着我们不必再遍历图表了。在那种情况下，我们将在 V 中积累的路径反转为 P，从 path/3.

得到 "returned"

注意：将检查递归终止的代码作为单独的规则放置几乎总是比使用 ;.

更清晰

求跳数最少的路径，可以从你想要的两点开始，找到所有路径，然后取最小的：

shortest_path(A,B,S) :-
    findall(P, path(A,B,P), Ps),
    maplist(prepend_length, Ps, Ls),
    sort(Ls, [[_,S]|_]).

prepend_length(P, [L,P]) :-
    length(P,L).

打印有向图中的最短路径

Printing the shortest path in a directed graph

prolog

shortest-path

graph-algorithm