Путь Дийкстра (не только расстояние)

Question

У меня есть код, который вычисляет минимальное расстояние пути Дийкстра. Можете ли вы мне помочь изменить свой код, чтобы не только печатать минимальное расстояние, но и полный путь?

% 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). 

Спасибо!
EDIT: Я редактировал свой код, потому что забыл добавить окрестности и предикаты края.

Answer 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). 

, что означает, что вы должны адаптировать все остальные пройти члены вида "Vertice-Distance-Origin".