为什么在这种未定义的情况下我对 Dijkstra 算法的实现会失败？
Why does my implementation of Dijkstra's algorithm fail under this undefined case?
我正在尝试在 Prolog（特别是 GNU Prolog）中编写 Dijkstra 算法的实现。首先，我做了一个事实 connection 来描述下图中的连接顶点。
现在看来我的实现适用于大约一半的测试用例，即这些：
s, k
g, h
e, c
但是对于这些，
h, g (this one has an empty Tentative_Connections)
c, e (this one too)
i, j (this one finds the incorrect path of [i, k, j])
失败了。
我的程序基于算法 wikipedia 页面上给出的描述。这是一些粗略的伪代码：
for a current node, find its connecting nodes
remove the ones that are visited
make a new list of nodes that factors in a tentative distance
delete the current node from the list of unvisited nodes
if the destination node is not in the unvisited list, the current built-up path is final
otherwise, recur on the node that is the closest regarding the tentative distance
但无论如何，我的代码总是失败（出现上述错误）。为了详细说明，这里是 h, g 案例的失败：
Unchartered = []
Tentative = []
Destination not reached
No tentative connections!
Closest = _1232
Closest = _1232
Next_Path = [h,b,s,c,l,i,k,j]
uncaught exception: error(instantiation_error,(is)/2)
| ?-
似乎在某一时刻，没有暂定点可供搜索。我不知道从这里做什么，因为维基百科没有详细说明这个问题。熟悉这个算法的人知道我可以做些什么来修复我的代码吗？
% https://www.youtube.com/watch?v=GazC3A4OQTE
% example graph
% cl; gprolog --consult-file dijkstra.pl --entry-goal main
connection(s, c, 3).
connection(c, l, 2).
connection(l, i, 4).
connection(l, j, 4).
connection(i, j, 6).
connection(i, k, 4).
connection(j, k, 4).
connection(k, e, 5).
connection(e, g, 2).
connection(g, h, 2).
connection(h, f, 3).
connection(f, d, 5).
connection(d, a, 4).
connection(b, d, 4).
connection(b, a, 3).
connection(b, s, 2).
connection(b, h, 1).
connection(a, s, 7).
get_vertices(_, Vertex_Count, Traversed, Traversed) :-
length(Traversed, Vertex_Count).
get_vertices([], _, Traversed, Traversed).
get_vertices([Vertex | Vertices], Vertex_Count, Traversed, Result) :-
get_vertices(Vertex, Vertex_Count, Traversed, More_Traversed),
get_vertices(Vertices, Vertex_Count, More_Traversed, Result).
get_vertices(Vertex, _, Traversed, Traversed) :-
atom(Vertex), member(Vertex, Traversed).
get_vertices(Vertex, Vertex_Count, Traversed, Result) :-
atom(Vertex),
findall(Connected, are_connected(Vertex, Connected, _), Vertices),
get_vertices(Vertices, Vertex_Count, [Vertex | Traversed], Result).
are_connected(A, B, S) :- connection(A, B, S) ; connection(B, A, S).
keep_unvisited([], _, []).
keep_unvisited([Connection | Connections], Unvisited, Result) :-
keep_unvisited(Connections, Unvisited, Tail_Result),
[Connection_Name, _] = Connection,
(member(Connection_Name, Unvisited) ->
Result = [Connection | Tail_Result];
Result = Tail_Result).
w_tentative_distances([], _, []).
w_tentative_distances([Connection | Connections], Node_Val, Result) :-
w_tentative_distances(Connections, Node_Val, Tail_Result),
[Connection_Name, Connection_Val] = Connection,
Tentative_Distance is Connection_Val + Node_Val,
(Connection_Val > Tentative_Distance ->
New_Distance = Tentative_Distance; New_Distance = Connection_Val),
Result = [[Connection_Name, New_Distance] | Tail_Result].
closest_node_([], Closest, Closest).
closest_node_([Node | Rest], Closest, Result) :-
[_, Node_Val] = Node,
[_, Closest_Val] = Closest,
(Node_Val < Closest_Val ->
closest_node_(Rest, Node, Result)
;
closest_node_(Rest, Closest, Result)).
closest_node([Node | Rest], Result) :-
closest_node_(Rest, Node, Result).
dijkstra([Node_Name, Node_Val], Unvisited, Dest_Node, Path, Final_Path) :-
findall([Connected, Dist], are_connected(Node_Name, Connected, Dist), Connections),
keep_unvisited(Connections, Unvisited, Unchartered_Connections),
w_tentative_distances(Unchartered_Connections, Node_Val, Tentative_Connections),
% trace,
delete(Unvisited, Node_Name, New_Unvisited),
format('Path = ~w\nNode_Name = ~w\nNode_Val = ~w\n', [Path, Node_Name, Node_Val]),
format('Unvisited = ~w\nNew_Unvisited = ~w\n', [Unvisited, New_Unvisited]),
% notrace,
format('Connections = ~w\n', [Connections]),
format('Unchartered = ~w\n', [Unchartered_Connections]),
format('Tentative = ~w\n', [Tentative_Connections]),
(member(Dest_Node, Unvisited) -> % destination has not been reached
write('Destination not reached\n'),
(closest_node(Tentative_Connections, Closest); write('No tentative connections!\n')),
format('Closest = ~w\n', [Closest]),
append(Path, [Node_Name], Next_Path),
format('Closest = ~w\nNext_Path = ~w\n', [Closest, Next_Path]),
dijkstra(Closest, New_Unvisited, Dest_Node, Next_Path, Final_Path);
write('The end was reached!\n'),
Final_Path = Path).
dijkstra_wrapper(Start, End, Vertex_Count, Path) :-
get_vertices(Start, Vertex_Count, [], Unvisited),
dijkstra([Start, 0], Unvisited, End, [], Path).
main :-
dijkstra_wrapper(h, g, 13, Path),
write(Path), nl.
非工作示例有一个不断增长的未访问列表（对于某些递归情况）
Path = [h,b,s,c,l,i,k]
Node_Name = j
Node_Val = 4
Unvisited = [g,e,j,a,d,f]
New_Unvisited = [g,e,a,d,f]
Connections = [[k,4],[l,4],[i,6]]
Unchartered = []
Tentative = []
Destination not reached
没有下行路径怎么办？
dijkstras 算法的主要思想是在已访问和未访问节点之间创建一个边界。一切都发生在边界。边界只是一对节点及其与起始节点的距离。在每一步中，未访问集合中与起点的总距离最小的节点被转移到已访问集合中。为此，检查从任何已访问节点到未访问节点的所有“连接”：到已访问节点的距离 + 连接值是总距离。这样你就可以获得从开始到目标的最小距离。请注意，此（主要是确定性的）算法适用于这两组而不是具体路径。但是，如果你想要一条路径，你还必须跟踪访问集中每个节点的源节点。
您的代码似乎有多个问题，我发现实施我自己的解决方案要容易得多。问题之一是起始节点出现在未访问列表中。您可以使用以下代码作为调试代码的参考：
minmember([A],A).
minmember([(E,N,S)|T],R):-
minmember(T,(Etmp,Ntmp,Stmp)),
( N>Ntmp
-> R=(Etmp,Ntmp,Stmp)
; R=(E,N,S)
).
boundary(Visited, (Connected, Dist, Node_Name), Unvisited):-
member((Node_Name, Value_to, _),Visited),
are_connected(Node_Name, Connected, Dist0),
member(Connected,Unvisited),
Dist is Dist0+Value_to.
boundary2path(B,Sink,[(Sink,Dist)]):-
member((Sink,Dist,start),B),
!.
boundary2path(B,Sink,[(Sink,Dist)|R]):-
member((Sink,Dist,Source),B),
boundary2path(B,Source,R).
dijkstra(Boundary, _, Dest_Node, Path):-
Boundary = [(Dest_Node,_,_)|_],
!,
format('Hit the end :) \n'),
boundary2path(Boundary,Dest_Node,Path),
format('Path found = ~w\n', [Path]).
dijkstra(Visited, Unvisited, Dest_Node, Path) :-
findall(E, boundary(Visited, E, Unvisited), Connections),
format('Connections = ~w\n', [Connections]),
minmember(Connections,(Node_Name,Dist,Source)),
format('Choosen = ~w\n', [(Node_Name,Dist,Source)]),
append(U1,[Node_Name|U2],Unvisited),
append(U1,U2,New_Unvisited),
format('New_Unvisited = ~w\n', [New_Unvisited]),
format('Visited = ~w\n', [[(Node_Name,Dist,Source)|Visited]]),
dijkstra([(Node_Name,Dist,Source)|Visited], New_Unvisited, Dest_Node, Path).
现在输出：
?- dijkstra([(h, 0, start)], [b, g, e, k, j, i, l, c, s, a, d, f], g, L).
Connections = [(f,3,h),(g,2,h),(b,1,h)]
Choosen = b,1,h
New_Unvisited = [g,e,k,j,i,l,c,s,a,d,f]
Visited = [(b,1,h),(h,0,start)]
Connections = [(d,5,b),(a,4,b),(s,3,b),(f,3,h),(g,2,h)]
Choosen = g,2,h
New_Unvisited = [e,k,j,i,l,c,s,a,d,f]
Visited = [(g,2,h),(b,1,h),(h,0,start)]
Hit the end :)
Path found = [(g,2),(h,0)]
L = [(g,2), (h,0)] ;
false.
对于目标 j 没有留下未访问的节点：
?- dijkstra([(h, 0, start)], [b, g, e, k, j, i, l, c, s, a, d, f], j, L).
...
Visited = [(i,12,l),(k,9,e),(l,8,c),(c,6,s),(d,5,b),(a,4,b),(e,4,g),(f,3,h),(s,3,b),(g,2,h),(b,1,h),(h,0,start)]
Connections = [(j,18,i),(j,13,k),(j,12,l)]
Choosen = j,12,l
New_Unvisited = []
Visited = [(j,12,l),(i,12,l),(k,9,e),(l,8,c),(c,6,s),(d,5,b),(a,4,b),(e,4,g),(f,3,h),(s,3,b),(g,2,h),(b,1,h),(h,0,start)]
Hit the end :)
Path found = [(j,12),(l,8),(c,6),(s,3),(b,1),(h,0)]
L = [(j,12), (l,8), (c,6), (s,3), (b,1), (h,0)] ;
false.
最后一个查询我画了一个边框的草图：
另一个。
它使用library(assoc) 关联列表来存储与每个顶点关联的路径。这避免了必须对列表扫描进行编码。 “接下来要访问的顶点”列表仍然是一个原始列表，但是我们需要消除重复的顶点并仅在每次访问后保留那些距离最小的顶点，然后按顶点距离对列表进行排序，以便下一个应该访问的顶点被访问是最重要的。
(SWI-Prolog 有一个内置的关联数据结构，SWI-Prolog dict，我在这里没有使用它。library(assoc) 存在于 GNU Prolog 中吗？它应该。 ..)
?- main.
VisitThese is currently: [0-a]
Neighbors of vertex a : [s-7,d-4,b-3]
Dirty visitations : [7-s,4-d,3-b], Clean visitations : [3-b,4-d,7-s]
VisitThese is currently: [3-b,4-d,7-s]
Neighbors of vertex b : [d-4,a-3,s-2,h-1]
Dirty visitations : [5-s,4-h,4-d,7-s], Clean visitations : [4-d,4-h,5-s]
VisitThese is currently: [4-d,4-h,5-s]
Neighbors of vertex d : [a-4,f-5,b-4]
Dirty visitations : [9-f,4-h,5-s], Clean visitations : [4-h,5-s,9-f]
VisitThese is currently: [4-h,5-s,9-f]
Neighbors of vertex h : [f-3,g-2,b-1]
Dirty visitations : [7-f,6-g,5-s,9-f], Clean visitations : [5-s,6-g,7-f]
VisitThese is currently: [5-s,6-g,7-f]
Neighbors of vertex s : [c-3,b-2,a-7]
Dirty visitations : [8-c,6-g,7-f], Clean visitations : [6-g,7-f,8-c]
VisitThese is currently: [6-g,7-f,8-c]
Neighbors of vertex g : [h-2,e-2]
Dirty visitations : [8-e,7-f,8-c], Clean visitations : [7-f,8-c,8-e]
VisitThese is currently: [7-f,8-c,8-e]
Neighbors of vertex f : [d-5,h-3]
Dirty visitations : [8-c,8-e], Clean visitations : [8-c,8-e]
VisitThese is currently: [8-c,8-e]
Neighbors of vertex c : [l-2,s-3]
Dirty visitations : [10-l,8-e], Clean visitations : [8-e,10-l]
VisitThese is currently: [8-e,10-l]
Neighbors of vertex e : [g-2,k-5]
Dirty visitations : [13-k,10-l], Clean visitations : [10-l,13-k]
VisitThese is currently: [10-l,13-k]
Neighbors of vertex l : [i-4,j-4,c-2]
Dirty visitations : [14-i,14-j,13-k], Clean visitations : [13-k,14-i,14-j]
VisitThese is currently: [13-k,14-i,14-j]
Neighbors of vertex k : [e-5,i-4,j-4]
Dirty visitations : [14-i,14-j], Clean visitations : [14-i,14-j]
VisitThese is currently: [14-i,14-j]
Neighbors of vertex i : [j-6,k-4,l-4]
Dirty visitations : [14-j], Clean visitations : [14-j]
VisitThese is currently: [14-j]
Neighbors of vertex j : [k-4,l-4,i-6]
Dirty visitations : [], Clean visitations : []
Vertex a is at distance 0 via [a-0]
Vertex b is at distance 3 via [a-0,b-3]
Vertex c is at distance 8 via [a-0,b-3,s-5,c-8]
Vertex d is at distance 4 via [a-0,d-4]
Vertex e is at distance 8 via [a-0,b-3,h-4,g-6,e-8]
Vertex f is at distance 7 via [a-0,b-3,h-4,f-7]
Vertex g is at distance 6 via [a-0,b-3,h-4,g-6]
Vertex h is at distance 4 via [a-0,b-3,h-4]
Vertex i is at distance 14 via [a-0,b-3,s-5,c-8,l-10,i-14]
Vertex j is at distance 14 via [a-0,b-3,s-5,c-8,l-10,j-14]
Vertex k is at distance 13 via [a-0,b-3,h-4,g-6,e-8,k-13]
Vertex l is at distance 10 via [a-0,b-3,s-5,c-8,l-10]
Vertex s is at distance 5 via [a-0,b-3,s-5]
计算方式：
% =========
% Graph definition
% =========
% ---------
% "Asymmetric connection relation"
% ---------
% "Connection relation" between vertices. Each edge is labeled with
% a "distance" (cost)
%
% connection(?VertexName1,?VertexName2,?Cost).
%
% This also indirectly defines the set of vertices which are simply
% given by their names, which are atoms.
%
% This relation is not symmetric. We make it symmetric by defining
% a symmetric relations "on top". Improvement: This relation could
% be made "canonical" in that a unique representation would be
% enforced by demanding that VertexName1 @=< VertexName (i.e. the
% vertex names would appear sorted by the standard order of terms).
connection(s, c, 3).
connection(c, l, 2).
connection(l, i, 4).
connection(l, j, 4).
connection(i, j, 6).
connection(i, k, 4).
connection(j, k, 4).
connection(k, e, 5).
connection(e, g, 2).
connection(g, h, 2).
connection(h, f, 3).
connection(f, d, 5).
connection(d, a, 4).
connection(b, d, 4).
connection(b, a, 3).
connection(b, s, 2).
connection(b, h, 1).
connection(a, s, 7).
% ---------
% "Symmetric connection relation"
% ---------
sym_connection(Vertex1,Vertex2,Cost) :- connection(Vertex1,Vertex2,Cost).
sym_connection(Vertex1,Vertex2,Cost) :- connection(Vertex2,Vertex1,Cost).
% =========
% Start measuring paths and their cost from vertex 'a'.
%
% Initially we only know about vertex 'a' itself
%
% - It is the only member in the list of vertices to be visited next,
% at distance/cost 0. This is represented by a single pair in list
% VisitThese: it is a list containing only [0-a].
% - We have a path to 'a' with overall distance/cost 0, containing only
% vertex 'a' found at cost 0: the path is [a-0].
% PathContainerIn maps 'a', the destination vertex, to that path
% [[a-0]].
% The container is implemented by an "association list" (a "map")
% from library(assoc); other abstract data types are possible, in
% particular SWI-Prolog's "dict" if this were running in SWI-Prolog.
% =========
main :-
list_to_assoc([a-[a-0]],PathContainerIn),
VisitThese=[0-a],
% Do it!
dijsktra(VisitThese,PathContainerIn,PathContainerOut),
% We are done! we just need to print out...
assoc_to_list(PathContainerOut,Pairs),
print_list(Pairs).
print_list([]).
print_list([Vertex-Path|More]) :-
reverse(Path,ReversedPath),
Path=[_-Dist|_],
format("Vertex ~q is at distance ~d via ~q~n",[Vertex,Dist,ReversedPath]),
print_list(More).
% =========
% dijsktra([CurCost-CurVertex|More],PathContainerIn,PathContainerOut).
%
% - The first argument is the "list of vertexes to be visited next", named
% "VisitThese" (i.e. the "boundary" of the search), sorted by the distance/cost
% of their path from the initial vertex, ascending (so we always need
% to just grab the head of "VisitThese" to find the vertex which is guaranteed
% nearest the start vertex on visit).
% - The second argument is the "container of the best-path-known-so-far to
% vertexes already seen (all of those visited or tentatively visited in
% handle_neighbors/7, for which a best-path-known-so-far could be determined)
% Note that a cheaper representation than keeping the full path would be
% to just keep the last edge of the path.
% The container is used to create a new container, accumulator-style, which
% is the third argument, which contains all the best paths to all the vertices
% at success-time.
% =========
dijsktra([],PathContainer,PathContainer) :- !.
dijsktra(VisitThese,PathContainerIn,PathContainerOut) :-
VisitThese = [CurCost-CurVertex|MoreToVisit],
format("VisitThese is currently: ~q ~n",[VisitThese]),
% bagof/3 fails if no neighbors, but that's only the case if the initial vertex is unconnected
bagof(LocalNeighbor-LocalCost,
sym_connection(CurVertex,LocalNeighbor,LocalCost),
Neighbors),
format("Neighbors of vertex ~q : ~q ~n",[CurVertex,Neighbors]),
get_assoc(CurVertex,PathContainerIn,CurPath),
% format("Found path for current vertex ~q: ~q~n",[CurVertex,CurPath]),
handle_neighbors(CurVertex,CurPath,CurCost,Neighbors,PathContainerIn,PathContainer2,VisitTheseToo),
append(VisitTheseToo,MoreToVisit,Dirty),
clean_visit_these_list(Dirty,Clean),
format("Dirty visitations : ~q, Clean visitations : ~q~n",[Dirty,Clean]),
dijsktra(Clean,PathContainer2,PathContainerOut).
% =========
% "Tentatively visit" all the neighbors of "CurVertex" ("CurVertex" can be reached through
% "CurPath" at cost "CurCost"), determining for each a path and overall cost
%
% We may reach a neighbor of "CurVertex":
%
% - for the first time if no path to it is stored in PathContainer yet.
% Then a new path is stored in PathContainer and the vertex is added to
% the list of vertexes-to-be-visted-next, "VisitThese" (which will have
% to be sorted by overall path cost before the recursive call to dijkstar/3)
% - for a not-the-first time if a path to it is stored in PathContainer yet
% (so the neighbor has been visited (and its old path is - by construction -
% cheaper and it shall not be visited again) or it has been only
% tentatively visited (and its old path *may* be costlier and thus demand
% replacement by the new path as well as addition of a cheaper
% entry in the list of vertexes to be visited next)
%
% Note that the list "Neighbors" also contains the neighboring vertex on
% the path "CurPath" through which "CurVertex" was reached in the first place.
% But there is no need to handle that case in a special way. This is just a
% vertex that has been visited previously and the old path is cheaper.
%
% handle_neighbors(+CurVertex,+CurPath,+CurCost,
% +Neighbors,
% +PathContainerIn,-PathContainerOut,
% -VisitThese)
%
% =========
% case of "all neighbor vertices handled, we are done"
handle_neighbors(_CurVertex,_CurPath,_CurCost,[],PathContainer,PathContainer,[]).
% case of "neighbor vertex already has a path but the new path is costlier
handle_neighbors(CurVertex,CurPath,CurCost,Neighbors,PathContainerIn,PathContainerOut,VisitThese) :-
Neighbors=[Vertex-LocalCost|More], % grab the next neighbor
get_assoc(Vertex,PathContainerIn,[Vertex-BestCostSoFar|_]), % grab its known path, if it exists (fails if not)
NewCost is CurCost+LocalCost,
NewCost >= BestCostSoFar, % the new path is costlier
!, % do nothing, move to next neighbor
handle_neighbors(CurVertex,CurPath,CurCost,More,PathContainerIn,PathContainerOut,VisitThese).
% case of "neighbor vertex already has a path but the new path is cheaper; note that it is added to the "VisitThese" list
handle_neighbors(CurVertex,CurPath,CurCost,Neighbors,PathContainerIn,PathContainerOut,[NewCost-Vertex|VisitThese]) :-
Neighbors=[Vertex-LocalCost|More], % grab the next neighbor
get_assoc(Vertex,PathContainerIn,[Vertex-BestCostSoFar|_]), % grab its known path, if it exists (fails if not)
NewCost is CurCost+LocalCost,
NewCost < BestCostSoFar, % new path is cheaper
!, % replace path, retain neighbor as "to be visited"
put_assoc(Vertex,PathContainerIn,[Vertex-NewCost|CurPath],PathContainer2),
handle_neighbors(CurVertex,CurPath,CurCost,More,PathContainer2,PathContainerOut,VisitThese).
% case of "neighbor vertex has no path yet"; note that it is added to the "VisitThese" list
handle_neighbors(CurVertex,CurPath,CurCost,Neighbors,PathContainerIn,PathContainerOut,[NewCost-Vertex|VisitThese]) :-
Neighbors=[Vertex-LocalCost|More], % grab the next neighbor
\+ get_assoc(Vertex,PathContainerIn,_), % vertex has no path yet
!, % the cut is not really needed
NewCost is CurCost+LocalCost,
put_assoc(Vertex,PathContainerIn,[Vertex-NewCost|CurPath],PathContainer2),
handle_neighbors(CurVertex,CurPath,CurCost,More,PathContainer2,PathContainerOut,VisitThese).
% ---
% Transfrom list of elements "Cost-Vertex"
%
% ... which is the list of vertexes and their "best cost yet" that
% shall be expanded by the Dijkstra algorithm, but in which several
% entries for the same "Vertex" may appear
% ... into a new list where there is always only exactly one entry for
% any "Vertex" appaearing in the original list, and the "Cost"
% associated to it is the minimum cost for that "Vertex".
% ---
clean_visit_these_list(Dirty,SortedByCostAsc) :-
predsort(sort_pairs,Dirty,SortedByVertexFirstCostSecond),
keep_best(SortedByVertexFirstCostSecond,DuplicatesRemovedMinCostRetained),
keysort(DuplicatesRemovedMinCostRetained,SortedByCostAsc).
sort_pairs(Order,Cost1-Vertex,Cost2-Vertex) :-
!, % Same vertex - order depends on associated cost
compare(Order,Cost1,Cost2).
sort_pairs(Order,_-Vertex1,_-Vertex2) :-
Vertex1 \== Vertex2,
!, % Different vertex - Sort lexicographically (cut is not needed actually)
compare(Order,Vertex1,Vertex2).
keep_best([Cost-Vertex,_-Vertex|More],Out) :-
!, % Vertex appears twice - retain only first entry (with smallest cost)
keep_best([Cost-Vertex|More],Out).
keep_best([Cost1-Vertex1,Cost2-Vertex2|More],[Cost1-Vertex1|Out]) :-
Vertex1 \== Vertex2,
!, % Different vertex - Retain first vertex and its cost, move on
keep_best([Cost2-Vertex2|More],Out).
keep_best([X],[X]). % Termination case #1
keep_best([],[]). % Termination case #2
% ---
% Test clean_visit_these_list/2
% ---
:- begin_tests(clean_visit_these_list).
test(1,true(Result == [])) :- clean_visit_these_list([],Result).
test(2,true(Result == [3-b])) :- clean_visit_these_list([3-b],Result).
test(2,true(Result == [3-b])) :- clean_visit_these_list([4-b,3-b,5-b],Result).
test(3,true(Result == [3-b,8-v,9-a,10-w])) :- clean_visit_these_list([8-v,10-w,9-a,3-b],Result).
test(4,true(Result == [2-w,3-b,8-v,9-a])) :- clean_visit_these_list([8-v,10-w,9-a,4-w,3-b,2-w,12-v],Result).
:- end_tests(clean_visit_these_list).
我正在尝试在 Prolog（特别是 GNU Prolog）中编写 Dijkstra 算法的实现。首先，我做了一个事实 connection 来描述下图中的连接顶点。
现在看来我的实现适用于大约一半的测试用例，即这些：
s, k
g, h
e, c
但是对于这些，
h, g (this one has an empty Tentative_Connections)
c, e (this one too)
i, j (this one finds the incorrect path of [i, k, j])
失败了。
我的程序基于算法 wikipedia 页面上给出的描述。这是一些粗略的伪代码：
for a current node, find its connecting nodes
remove the ones that are visited
make a new list of nodes that factors in a tentative distance
delete the current node from the list of unvisited nodes
if the destination node is not in the unvisited list, the current built-up path is final
otherwise, recur on the node that is the closest regarding the tentative distance
但无论如何，我的代码总是失败（出现上述错误）。为了详细说明，这里是 h, g 案例的失败：
Unchartered = []
Tentative = []
Destination not reached
No tentative connections!
Closest = _1232
Closest = _1232
Next_Path = [h,b,s,c,l,i,k,j]
uncaught exception: error(instantiation_error,(is)/2)
| ?-
似乎在某一时刻，没有暂定点可供搜索。我不知道从这里做什么，因为维基百科没有详细说明这个问题。熟悉这个算法的人知道我可以做些什么来修复我的代码吗？
% https://www.youtube.com/watch?v=GazC3A4OQTE
% example graph
% cl; gprolog --consult-file dijkstra.pl --entry-goal main
connection(s, c, 3).
connection(c, l, 2).
connection(l, i, 4).
connection(l, j, 4).
connection(i, j, 6).
connection(i, k, 4).
connection(j, k, 4).
connection(k, e, 5).
connection(e, g, 2).
connection(g, h, 2).
connection(h, f, 3).
connection(f, d, 5).
connection(d, a, 4).
connection(b, d, 4).
connection(b, a, 3).
connection(b, s, 2).
connection(b, h, 1).
connection(a, s, 7).
get_vertices(_, Vertex_Count, Traversed, Traversed) :-
length(Traversed, Vertex_Count).
get_vertices([], _, Traversed, Traversed).
get_vertices([Vertex | Vertices], Vertex_Count, Traversed, Result) :-
get_vertices(Vertex, Vertex_Count, Traversed, More_Traversed),
get_vertices(Vertices, Vertex_Count, More_Traversed, Result).
get_vertices(Vertex, _, Traversed, Traversed) :-
atom(Vertex), member(Vertex, Traversed).
get_vertices(Vertex, Vertex_Count, Traversed, Result) :-
atom(Vertex),
findall(Connected, are_connected(Vertex, Connected, _), Vertices),
get_vertices(Vertices, Vertex_Count, [Vertex | Traversed], Result).
are_connected(A, B, S) :- connection(A, B, S) ; connection(B, A, S).
keep_unvisited([], _, []).
keep_unvisited([Connection | Connections], Unvisited, Result) :-
keep_unvisited(Connections, Unvisited, Tail_Result),
[Connection_Name, _] = Connection,
(member(Connection_Name, Unvisited) ->
Result = [Connection | Tail_Result];
Result = Tail_Result).
w_tentative_distances([], _, []).
w_tentative_distances([Connection | Connections], Node_Val, Result) :-
w_tentative_distances(Connections, Node_Val, Tail_Result),
[Connection_Name, Connection_Val] = Connection,
Tentative_Distance is Connection_Val + Node_Val,
(Connection_Val > Tentative_Distance ->
New_Distance = Tentative_Distance; New_Distance = Connection_Val),
Result = [[Connection_Name, New_Distance] | Tail_Result].
closest_node_([], Closest, Closest).
closest_node_([Node | Rest], Closest, Result) :-
[_, Node_Val] = Node,
[_, Closest_Val] = Closest,
(Node_Val < Closest_Val ->
closest_node_(Rest, Node, Result)
;
closest_node_(Rest, Closest, Result)).
closest_node([Node | Rest], Result) :-
closest_node_(Rest, Node, Result).
dijkstra([Node_Name, Node_Val], Unvisited, Dest_Node, Path, Final_Path) :-
findall([Connected, Dist], are_connected(Node_Name, Connected, Dist), Connections),
keep_unvisited(Connections, Unvisited, Unchartered_Connections),
w_tentative_distances(Unchartered_Connections, Node_Val, Tentative_Connections),
% trace,
delete(Unvisited, Node_Name, New_Unvisited),
format('Path = ~w\nNode_Name = ~w\nNode_Val = ~w\n', [Path, Node_Name, Node_Val]),
format('Unvisited = ~w\nNew_Unvisited = ~w\n', [Unvisited, New_Unvisited]),
% notrace,
format('Connections = ~w\n', [Connections]),
format('Unchartered = ~w\n', [Unchartered_Connections]),
format('Tentative = ~w\n', [Tentative_Connections]),
(member(Dest_Node, Unvisited) -> % destination has not been reached
write('Destination not reached\n'),
(closest_node(Tentative_Connections, Closest); write('No tentative connections!\n')),
format('Closest = ~w\n', [Closest]),
append(Path, [Node_Name], Next_Path),
format('Closest = ~w\nNext_Path = ~w\n', [Closest, Next_Path]),
dijkstra(Closest, New_Unvisited, Dest_Node, Next_Path, Final_Path);
write('The end was reached!\n'),
Final_Path = Path).
dijkstra_wrapper(Start, End, Vertex_Count, Path) :-
get_vertices(Start, Vertex_Count, [], Unvisited),
dijkstra([Start, 0], Unvisited, End, [], Path).
main :-
dijkstra_wrapper(h, g, 13, Path),
write(Path), nl.
非工作示例有一个不断增长的未访问列表（对于某些递归情况）
Path = [h,b,s,c,l,i,k]
Node_Name = j
Node_Val = 4
Unvisited = [g,e,j,a,d,f]
New_Unvisited = [g,e,a,d,f]
Connections = [[k,4],[l,4],[i,6]]
Unchartered = []
Tentative = []
Destination not reached
没有下行路径怎么办？
dijkstras 算法的主要思想是在已访问和未访问节点之间创建一个边界。一切都发生在边界。边界只是一对节点及其与起始节点的距离。在每一步中，未访问集合中与起点的总距离最小的节点被转移到已访问集合中。为此，检查从任何已访问节点到未访问节点的所有“连接”：到已访问节点的距离 + 连接值是总距离。这样你就可以获得从开始到目标的最小距离。请注意，此（主要是确定性的）算法适用于这两组而不是具体路径。但是，如果你想要一条路径，你还必须跟踪访问集中每个节点的源节点。
您的代码似乎有多个问题，我发现实施我自己的解决方案要容易得多。问题之一是起始节点出现在未访问列表中。您可以使用以下代码作为调试代码的参考：
minmember([A],A).
minmember([(E,N,S)|T],R):-
minmember(T,(Etmp,Ntmp,Stmp)),
( N>Ntmp
-> R=(Etmp,Ntmp,Stmp)
; R=(E,N,S)
).
boundary(Visited, (Connected, Dist, Node_Name), Unvisited):-
member((Node_Name, Value_to, _),Visited),
are_connected(Node_Name, Connected, Dist0),
member(Connected,Unvisited),
Dist is Dist0+Value_to.
boundary2path(B,Sink,[(Sink,Dist)]):-
member((Sink,Dist,start),B),
!.
boundary2path(B,Sink,[(Sink,Dist)|R]):-
member((Sink,Dist,Source),B),
boundary2path(B,Source,R).
dijkstra(Boundary, _, Dest_Node, Path):-
Boundary = [(Dest_Node,_,_)|_],
!,
format('Hit the end :) \n'),
boundary2path(Boundary,Dest_Node,Path),
format('Path found = ~w\n', [Path]).
dijkstra(Visited, Unvisited, Dest_Node, Path) :-
findall(E, boundary(Visited, E, Unvisited), Connections),
format('Connections = ~w\n', [Connections]),
minmember(Connections,(Node_Name,Dist,Source)),
format('Choosen = ~w\n', [(Node_Name,Dist,Source)]),
append(U1,[Node_Name|U2],Unvisited),
append(U1,U2,New_Unvisited),
format('New_Unvisited = ~w\n', [New_Unvisited]),
format('Visited = ~w\n', [[(Node_Name,Dist,Source)|Visited]]),
dijkstra([(Node_Name,Dist,Source)|Visited], New_Unvisited, Dest_Node, Path).
现在输出：
?- dijkstra([(h, 0, start)], [b, g, e, k, j, i, l, c, s, a, d, f], g, L).
Connections = [(f,3,h),(g,2,h),(b,1,h)]
Choosen = b,1,h
New_Unvisited = [g,e,k,j,i,l,c,s,a,d,f]
Visited = [(b,1,h),(h,0,start)]
Connections = [(d,5,b),(a,4,b),(s,3,b),(f,3,h),(g,2,h)]
Choosen = g,2,h
New_Unvisited = [e,k,j,i,l,c,s,a,d,f]
Visited = [(g,2,h),(b,1,h),(h,0,start)]
Hit the end :)
Path found = [(g,2),(h,0)]
L = [(g,2), (h,0)] ;
false.
对于目标 j 没有留下未访问的节点：
?- dijkstra([(h, 0, start)], [b, g, e, k, j, i, l, c, s, a, d, f], j, L).
...
Visited = [(i,12,l),(k,9,e),(l,8,c),(c,6,s),(d,5,b),(a,4,b),(e,4,g),(f,3,h),(s,3,b),(g,2,h),(b,1,h),(h,0,start)]
Connections = [(j,18,i),(j,13,k),(j,12,l)]
Choosen = j,12,l
New_Unvisited = []
Visited = [(j,12,l),(i,12,l),(k,9,e),(l,8,c),(c,6,s),(d,5,b),(a,4,b),(e,4,g),(f,3,h),(s,3,b),(g,2,h),(b,1,h),(h,0,start)]
Hit the end :)
Path found = [(j,12),(l,8),(c,6),(s,3),(b,1),(h,0)]
L = [(j,12), (l,8), (c,6), (s,3), (b,1), (h,0)] ;
false.
最后一个查询我画了一个边框的草图：
另一个。
它使用library(assoc) 关联列表来存储与每个顶点关联的路径。这避免了必须对列表扫描进行编码。 “接下来要访问的顶点”列表仍然是一个原始列表，但是我们需要消除重复的顶点并仅在每次访问后保留那些距离最小的顶点，然后按顶点距离对列表进行排序，以便下一个应该访问的顶点被访问是最重要的。
(SWI-Prolog 有一个内置的关联数据结构，SWI-Prolog dict，我在这里没有使用它。library(assoc) 存在于 GNU Prolog 中吗？它应该。 ..)
?- main.
VisitThese is currently: [0-a]
Neighbors of vertex a : [s-7,d-4,b-3]
Dirty visitations : [7-s,4-d,3-b], Clean visitations : [3-b,4-d,7-s]
VisitThese is currently: [3-b,4-d,7-s]
Neighbors of vertex b : [d-4,a-3,s-2,h-1]
Dirty visitations : [5-s,4-h,4-d,7-s], Clean visitations : [4-d,4-h,5-s]
VisitThese is currently: [4-d,4-h,5-s]
Neighbors of vertex d : [a-4,f-5,b-4]
Dirty visitations : [9-f,4-h,5-s], Clean visitations : [4-h,5-s,9-f]
VisitThese is currently: [4-h,5-s,9-f]
Neighbors of vertex h : [f-3,g-2,b-1]
Dirty visitations : [7-f,6-g,5-s,9-f], Clean visitations : [5-s,6-g,7-f]
VisitThese is currently: [5-s,6-g,7-f]
Neighbors of vertex s : [c-3,b-2,a-7]
Dirty visitations : [8-c,6-g,7-f], Clean visitations : [6-g,7-f,8-c]
VisitThese is currently: [6-g,7-f,8-c]
Neighbors of vertex g : [h-2,e-2]
Dirty visitations : [8-e,7-f,8-c], Clean visitations : [7-f,8-c,8-e]
VisitThese is currently: [7-f,8-c,8-e]
Neighbors of vertex f : [d-5,h-3]
Dirty visitations : [8-c,8-e], Clean visitations : [8-c,8-e]
VisitThese is currently: [8-c,8-e]
Neighbors of vertex c : [l-2,s-3]
Dirty visitations : [10-l,8-e], Clean visitations : [8-e,10-l]
VisitThese is currently: [8-e,10-l]
Neighbors of vertex e : [g-2,k-5]
Dirty visitations : [13-k,10-l], Clean visitations : [10-l,13-k]
VisitThese is currently: [10-l,13-k]
Neighbors of vertex l : [i-4,j-4,c-2]
Dirty visitations : [14-i,14-j,13-k], Clean visitations : [13-k,14-i,14-j]
VisitThese is currently: [13-k,14-i,14-j]
Neighbors of vertex k : [e-5,i-4,j-4]
Dirty visitations : [14-i,14-j], Clean visitations : [14-i,14-j]
VisitThese is currently: [14-i,14-j]
Neighbors of vertex i : [j-6,k-4,l-4]
Dirty visitations : [14-j], Clean visitations : [14-j]
VisitThese is currently: [14-j]
Neighbors of vertex j : [k-4,l-4,i-6]
Dirty visitations : [], Clean visitations : []
Vertex a is at distance 0 via [a-0]
Vertex b is at distance 3 via [a-0,b-3]
Vertex c is at distance 8 via [a-0,b-3,s-5,c-8]
Vertex d is at distance 4 via [a-0,d-4]
Vertex e is at distance 8 via [a-0,b-3,h-4,g-6,e-8]
Vertex f is at distance 7 via [a-0,b-3,h-4,f-7]
Vertex g is at distance 6 via [a-0,b-3,h-4,g-6]
Vertex h is at distance 4 via [a-0,b-3,h-4]
Vertex i is at distance 14 via [a-0,b-3,s-5,c-8,l-10,i-14]
Vertex j is at distance 14 via [a-0,b-3,s-5,c-8,l-10,j-14]
Vertex k is at distance 13 via [a-0,b-3,h-4,g-6,e-8,k-13]
Vertex l is at distance 10 via [a-0,b-3,s-5,c-8,l-10]
Vertex s is at distance 5 via [a-0,b-3,s-5]
计算方式：
% =========
% Graph definition
% =========
% ---------
% "Asymmetric connection relation"
% ---------
% "Connection relation" between vertices. Each edge is labeled with
% a "distance" (cost)
%
% connection(?VertexName1,?VertexName2,?Cost).
%
% This also indirectly defines the set of vertices which are simply
% given by their names, which are atoms.
%
% This relation is not symmetric. We make it symmetric by defining
% a symmetric relations "on top". Improvement: This relation could
% be made "canonical" in that a unique representation would be
% enforced by demanding that VertexName1 @=< VertexName (i.e. the
% vertex names would appear sorted by the standard order of terms).
connection(s, c, 3).
connection(c, l, 2).
connection(l, i, 4).
connection(l, j, 4).
connection(i, j, 6).
connection(i, k, 4).
connection(j, k, 4).
connection(k, e, 5).
connection(e, g, 2).
connection(g, h, 2).
connection(h, f, 3).
connection(f, d, 5).
connection(d, a, 4).
connection(b, d, 4).
connection(b, a, 3).
connection(b, s, 2).
connection(b, h, 1).
connection(a, s, 7).
% ---------
% "Symmetric connection relation"
% ---------
sym_connection(Vertex1,Vertex2,Cost) :- connection(Vertex1,Vertex2,Cost).
sym_connection(Vertex1,Vertex2,Cost) :- connection(Vertex2,Vertex1,Cost).
% =========
% Start measuring paths and their cost from vertex 'a'.
%
% Initially we only know about vertex 'a' itself
%
% - It is the only member in the list of vertices to be visited next,
% at distance/cost 0. This is represented by a single pair in list
% VisitThese: it is a list containing only [0-a].
% - We have a path to 'a' with overall distance/cost 0, containing only
% vertex 'a' found at cost 0: the path is [a-0].
% PathContainerIn maps 'a', the destination vertex, to that path
% [[a-0]].
% The container is implemented by an "association list" (a "map")
% from library(assoc); other abstract data types are possible, in
% particular SWI-Prolog's "dict" if this were running in SWI-Prolog.
% =========
main :-
list_to_assoc([a-[a-0]],PathContainerIn),
VisitThese=[0-a],
% Do it!
dijsktra(VisitThese,PathContainerIn,PathContainerOut),
% We are done! we just need to print out...
assoc_to_list(PathContainerOut,Pairs),
print_list(Pairs).
print_list([]).
print_list([Vertex-Path|More]) :-
reverse(Path,ReversedPath),
Path=[_-Dist|_],
format("Vertex ~q is at distance ~d via ~q~n",[Vertex,Dist,ReversedPath]),
print_list(More).
% =========
% dijsktra([CurCost-CurVertex|More],PathContainerIn,PathContainerOut).
%
% - The first argument is the "list of vertexes to be visited next", named
% "VisitThese" (i.e. the "boundary" of the search), sorted by the distance/cost
% of their path from the initial vertex, ascending (so we always need
% to just grab the head of "VisitThese" to find the vertex which is guaranteed
% nearest the start vertex on visit).
% - The second argument is the "container of the best-path-known-so-far to
% vertexes already seen (all of those visited or tentatively visited in
% handle_neighbors/7, for which a best-path-known-so-far could be determined)
% Note that a cheaper representation than keeping the full path would be
% to just keep the last edge of the path.
% The container is used to create a new container, accumulator-style, which
% is the third argument, which contains all the best paths to all the vertices
% at success-time.
% =========
dijsktra([],PathContainer,PathContainer) :- !.
dijsktra(VisitThese,PathContainerIn,PathContainerOut) :-
VisitThese = [CurCost-CurVertex|MoreToVisit],
format("VisitThese is currently: ~q ~n",[VisitThese]),
% bagof/3 fails if no neighbors, but that's only the case if the initial vertex is unconnected
bagof(LocalNeighbor-LocalCost,
sym_connection(CurVertex,LocalNeighbor,LocalCost),
Neighbors),
format("Neighbors of vertex ~q : ~q ~n",[CurVertex,Neighbors]),
get_assoc(CurVertex,PathContainerIn,CurPath),
% format("Found path for current vertex ~q: ~q~n",[CurVertex,CurPath]),
handle_neighbors(CurVertex,CurPath,CurCost,Neighbors,PathContainerIn,PathContainer2,VisitTheseToo),
append(VisitTheseToo,MoreToVisit,Dirty),
clean_visit_these_list(Dirty,Clean),
format("Dirty visitations : ~q, Clean visitations : ~q~n",[Dirty,Clean]),
dijsktra(Clean,PathContainer2,PathContainerOut).
% =========
% "Tentatively visit" all the neighbors of "CurVertex" ("CurVertex" can be reached through
% "CurPath" at cost "CurCost"), determining for each a path and overall cost
%
% We may reach a neighbor of "CurVertex":
%
% - for the first time if no path to it is stored in PathContainer yet.
% Then a new path is stored in PathContainer and the vertex is added to
% the list of vertexes-to-be-visted-next, "VisitThese" (which will have
% to be sorted by overall path cost before the recursive call to dijkstar/3)
% - for a not-the-first time if a path to it is stored in PathContainer yet
% (so the neighbor has been visited (and its old path is - by construction -
% cheaper and it shall not be visited again) or it has been only
% tentatively visited (and its old path *may* be costlier and thus demand
% replacement by the new path as well as addition of a cheaper
% entry in the list of vertexes to be visited next)
%
% Note that the list "Neighbors" also contains the neighboring vertex on
% the path "CurPath" through which "CurVertex" was reached in the first place.
% But there is no need to handle that case in a special way. This is just a
% vertex that has been visited previously and the old path is cheaper.
%
% handle_neighbors(+CurVertex,+CurPath,+CurCost,
% +Neighbors,
% +PathContainerIn,-PathContainerOut,
% -VisitThese)
%
% =========
% case of "all neighbor vertices handled, we are done"
handle_neighbors(_CurVertex,_CurPath,_CurCost,[],PathContainer,PathContainer,[]).
% case of "neighbor vertex already has a path but the new path is costlier
handle_neighbors(CurVertex,CurPath,CurCost,Neighbors,PathContainerIn,PathContainerOut,VisitThese) :-
Neighbors=[Vertex-LocalCost|More], % grab the next neighbor
get_assoc(Vertex,PathContainerIn,[Vertex-BestCostSoFar|_]), % grab its known path, if it exists (fails if not)
NewCost is CurCost+LocalCost,
NewCost >= BestCostSoFar, % the new path is costlier
!, % do nothing, move to next neighbor
handle_neighbors(CurVertex,CurPath,CurCost,More,PathContainerIn,PathContainerOut,VisitThese).
% case of "neighbor vertex already has a path but the new path is cheaper; note that it is added to the "VisitThese" list
handle_neighbors(CurVertex,CurPath,CurCost,Neighbors,PathContainerIn,PathContainerOut,[NewCost-Vertex|VisitThese]) :-
Neighbors=[Vertex-LocalCost|More], % grab the next neighbor
get_assoc(Vertex,PathContainerIn,[Vertex-BestCostSoFar|_]), % grab its known path, if it exists (fails if not)
NewCost is CurCost+LocalCost,
NewCost < BestCostSoFar, % new path is cheaper
!, % replace path, retain neighbor as "to be visited"
put_assoc(Vertex,PathContainerIn,[Vertex-NewCost|CurPath],PathContainer2),
handle_neighbors(CurVertex,CurPath,CurCost,More,PathContainer2,PathContainerOut,VisitThese).
% case of "neighbor vertex has no path yet"; note that it is added to the "VisitThese" list
handle_neighbors(CurVertex,CurPath,CurCost,Neighbors,PathContainerIn,PathContainerOut,[NewCost-Vertex|VisitThese]) :-
Neighbors=[Vertex-LocalCost|More], % grab the next neighbor
\+ get_assoc(Vertex,PathContainerIn,_), % vertex has no path yet
!, % the cut is not really needed
NewCost is CurCost+LocalCost,
put_assoc(Vertex,PathContainerIn,[Vertex-NewCost|CurPath],PathContainer2),
handle_neighbors(CurVertex,CurPath,CurCost,More,PathContainer2,PathContainerOut,VisitThese).
% ---
% Transfrom list of elements "Cost-Vertex"
%
% ... which is the list of vertexes and their "best cost yet" that
% shall be expanded by the Dijkstra algorithm, but in which several
% entries for the same "Vertex" may appear
% ... into a new list where there is always only exactly one entry for
% any "Vertex" appaearing in the original list, and the "Cost"
% associated to it is the minimum cost for that "Vertex".
% ---
clean_visit_these_list(Dirty,SortedByCostAsc) :-
predsort(sort_pairs,Dirty,SortedByVertexFirstCostSecond),
keep_best(SortedByVertexFirstCostSecond,DuplicatesRemovedMinCostRetained),
keysort(DuplicatesRemovedMinCostRetained,SortedByCostAsc).
sort_pairs(Order,Cost1-Vertex,Cost2-Vertex) :-
!, % Same vertex - order depends on associated cost
compare(Order,Cost1,Cost2).
sort_pairs(Order,_-Vertex1,_-Vertex2) :-
Vertex1 \== Vertex2,
!, % Different vertex - Sort lexicographically (cut is not needed actually)
compare(Order,Vertex1,Vertex2).
keep_best([Cost-Vertex,_-Vertex|More],Out) :-
!, % Vertex appears twice - retain only first entry (with smallest cost)
keep_best([Cost-Vertex|More],Out).
keep_best([Cost1-Vertex1,Cost2-Vertex2|More],[Cost1-Vertex1|Out]) :-
Vertex1 \== Vertex2,
!, % Different vertex - Retain first vertex and its cost, move on
keep_best([Cost2-Vertex2|More],Out).
keep_best([X],[X]). % Termination case #1
keep_best([],[]). % Termination case #2
% ---
% Test clean_visit_these_list/2
% ---
:- begin_tests(clean_visit_these_list).
test(1,true(Result == [])) :- clean_visit_these_list([],Result).
test(2,true(Result == [3-b])) :- clean_visit_these_list([3-b],Result).
test(2,true(Result == [3-b])) :- clean_visit_these_list([4-b,3-b,5-b],Result).
test(3,true(Result == [3-b,8-v,9-a,10-w])) :- clean_visit_these_list([8-v,10-w,9-a,3-b],Result).
test(4,true(Result == [2-w,3-b,8-v,9-a])) :- clean_visit_these_list([8-v,10-w,9-a,4-w,3-b,2-w,12-v],Result).
:- end_tests(clean_visit_these_list).