0

我有计算 Dijkstra 路径最小距离的代码。你能帮我编辑我的代码，以便不仅打印最小距离，还打印完整路径吗？

% min_dist(+Graph,+Start,-MinDist)
min_dist(Graph,Start,MinDist):-
   dijkstra(Graph,[],[Start-0],MinDist).

edge(g(Es,Vs),V1,V2,Value):-
   member(e(V1,V2,Value),Vs) ;
   member(e(V2,V1,Value),Vs).

neighbourhood(Graph,V,NB):-
   setof(V1-E,edge(Graph,V,V1,E),NB).

% dijkstra(+Graph,+ClosedVertices,+OpenVertices,-Distances)
dijkstra(_,MinDist,[],MinDist).
dijkstra(Graph,Closed,Open,MinDist):-
   choose_v(Open,V-D,RestOpen),
   neighbourhood(Graph,V,NB),  % NB is a list of adjacent vertices+distance to V
   diff(NB,Closed,NewNB),
   merge(NewNB,RestOpen,D,NewOpen),
   dijkstra(Graph,[V-D|Closed],NewOpen,MinDist).

% choose_v(+OpenVertices,-VertexToExpand,-RestOpenVertices)
choose_v([H|T],MinV,Rest):-
   choose_minv(T,H,MinV,Rest).
choose_minv([],MinV,MinV,[]).
choose_minv([H|T],M,MinV,[H2|Rest]):-
   H=V1-D1, M=V-D,
   (D1<D -> NextM=H,H2=M
          ; NextM=M,H2=H),
   choose_minv(T,NextM,MinV,Rest).

% diff(+ListOfVertices,+Closed,-ListOfNonClosedVertices)
diff([],_,[]).
diff([H|T],Closed,L):-
   H=V-D,
   (member(V-_,Closed) -> L=NewT ; L=[H|NewT]),
   diff(T,Closed,NewT).

% merge(+ListOfVertices,+OldOpenVertices,-AllOpenVertices)
merge([],L,_,L).
merge([V1-D1|T],Open,D,NewOpen):-
   (remove(Open,V1-D2,RestOpen)
      -> VD is min(D2,D+D1)
       ; RestOpen=Open,VD is D+D1),
   NewOpen=[V1-VD|SubOpen],
   merge(T,RestOpen,D,SubOpen).

remove([H|T],H,T).
remove([H|T],X,[H|NT]):-
   H\=X,
   remove(T,X,NT).

谢谢！
编辑：我已经编辑了我的代码，因为我忘记添加邻域和边缘谓词。

4

1 回答 1

1

很好的来源，组织良好，评论很好。

我建议您修改您的“合并”语句，以便不仅更新最小距离，还包括第三个字段，其中包含提供此最小值的顶点。

（警告：对这些陈述的评论缺少一个论据）。

就像是：

merge([V1-D1|T],Open,V-D-_,[V1-VD-O|SubOpen]):-
   (remove(Open,V1-D2-O2,RestOpen)
      -> ( D2<D+D1 -> VD=D2, O=O2 ; VD is D+D1, O=V)
      ; RestOpen=Open,VD is D+D1,O=V),
   merge(T,RestOpen,D,SubOpen).

这意味着您必须调整所有剩余部分以传递“顶点-距离-原点”形式的术语。

于 2015-05-22T18:59:26.370 回答