Why does my implementation of Dijkstra's algorithm fail under this undefined case?

Question

I am trying to write an implementation of Dijkstra's Algorithm in Prolog (specifically, GNU Prolog). To begin, I made a fact connection that describes the connected vertices of the graph below.

It now seems like my implementation works for around half of my test cases, namely these:

s, k
g, h
e, c

But for these,

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])

it fails.

I based my program on the description given on the algorithm's wikipedia page. Here is some rough psuedocode:

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

But no matter what, my code keeps failing (with the errors above). To elaborate on that, here is the failure for the h, g case:

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)
| ?- 

It seems like at one point, there are no tentative points left to search. I do not know what to do from here, as Wikipedia does not elaborate on this issue. Does anyone who knows this algorithm well know what I can do to fix my code?

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

The non-working examples have an ever-growing Unvisited list (for some recursive cases)

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

What do I do if there are no paths to travel down?

Answer 1

The main idea of dijkstras algorithm is to create a boundary between visited and unvisited nodes. Everything happens in the boundary. The boundary are simply pairs of nodes and their distances from the start node. In each step the node from the unvistied set with the smallest total distance from the start is transfered to the vistied set. To do this all "connections" from any visited nodes to unvisited nodes are checked: distance to the vistited node + connection value is the total distance. This way you can get the minimal distance from start to goal. Please note that this (mostly deterministic) algorithm works with those two sets rather than a concrete path. However if you want to have a path you have to keep track of the source node for each node in the visited set as well.

Your code seems to have multiple issues and I found it way easier just to implement my own solution. One of the problems is that the start node appears in the unvistied list. You can use the following code as a reference to debug your code:

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

Now the output for:

?- 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.

For the goal j no unvisited nodes are left:

?- 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.

​For the last query I made a sketch for the border: