如何使用加权图在序言中找到最短路径
How to find shortest path in prolog with weighted graph
我有这个代码：
link(a,b,4).
link(a,c,2).
link(b,g,5).
link(c,g,6).
link(c,d,5).
link(d,g,3).
path(S,D,TDist):-
link(S,D,TDist).
path(S,D,TDist):-
link(S,X,TD1), path(X,D,TD2), TDist=TD1+TD2.
这将遵循深度优先搜索策略，但结果是它会给我所有路径，并且不会显示哪条路径最短。是否仍然可以使用该策略并找到最短路径？如果不是，使用什么搜索策略？以及如何实现它。
我认为你的代码有问题：
TDist=TD1+TD2 不计算总和，使用 is/2 代替，至少在返回路径时是这样。
如果图中有环会循环，但假设数据实际上是DAG，我们现在可以忽略。
我们不能说实际路径是什么，只能说它的值。
总之，library(aggregate)可以用来求最短路径。例如
?- aggregate(min(D), path(a,g,D), D).
D = 8.
或者，由于 gnu-prolog 没有 library(aggregate)，取由 setof/3 计算的第一个元素：
?- setof(D, path(a,g,D), [Min|Rest]).
Min = 8,
Rest = [9, 10].
我有这个代码：
link(a,b,4).
link(a,c,2).
link(b,g,5).
link(c,g,6).
link(c,d,5).
link(d,g,3).
path(S,D,TDist):-
link(S,D,TDist).
path(S,D,TDist):-
link(S,X,TD1), path(X,D,TD2), TDist=TD1+TD2.
这将遵循深度优先搜索策略，但结果是它会给我所有路径，并且不会显示哪条路径最短。是否仍然可以使用该策略并找到最短路径？如果不是，使用什么搜索策略？以及如何实现它。
我认为你的代码有问题：
TDist=TD1+TD2不计算总和，使用 is/2 代替，至少在返回路径时是这样。如果图中有环会循环，但假设数据实际上是DAG，我们现在可以忽略。
我们不能说实际路径是什么，只能说它的值。
总之，library(aggregate)可以用来求最短路径。例如
?- aggregate(min(D), path(a,g,D), D).
D = 8.
或者，由于 gnu-prolog 没有 library(aggregate)，取由 setof/3 计算的第一个元素：
?- setof(D, path(a,g,D), [Min|Rest]).
Min = 8,
Rest = [9, 10].