title: How to find the unique shortest path for a weighted directed graph with SWI Prolog?
body: <p>This is an extension of what I did in Prolog class. In class, I was asked to write a predicate <code>path(X, Y, N)</code> which returns true if and only there is a path from node <code>X</code> to node <code>Y</code> with length <code>N</code>. What is given is the list of directed edges with corresponding weights, e.g. <code>edge(a, b, 3)</code> and <code>edge(c, d, 10)</code>.</p>
  
  <p>The given problem is pretty straightforward (only some recursion and base cases). However, I thought that maybe I could extend this a little further. Given that the simple directed graph input may contain cycles and contains only non-negative weights, what is the length of the <em>unique shortest path</em> from given nodes <code>A</code> and <code>B</code>. (By <em>unique</em>, I mean that this predicate should return false if more than one shortest path exists from <code>A</code> to <code>B</code>).</p>
  
  <p>Here is an example of the database which contains a cycle (a, b, c, e, a).</p>
  
  <pre><code>edge(a, b, 1).
  edge(b, c, 2).
  edge(c, d, 1).
  edge(b, d, 4).
  edge(c, e, 1).
  edge(e, a, 10).
  edge(e, d, 6).
  </code></pre>
  
  <p>I thought that to satisfy the <em>unique</em> condition, I thought that I should augment the original <code>path/3</code> predicate to also contain the path information as a list (so that I could compare the path uniqueness later). This new augmentation is reflected in the new <code>path/4</code> predicate.</p>
  
  <pre><code>path(X, X, 0, []).
  path(X, Y, N, [Y]) :- edge(X, Y, N).
  path(X, Y, N, [Z|T]) :- edge(X, Z, N1), N2 is N - N1, N2 &gt; 0, path(Z, Y, N2, T).
  
  path(X, Y, N) :- path(X, Y, N, _).
  </code></pre>
  
  <p>As of this code, I already found a problem: if I try to unify the predicate with <code>path(a, b, N, Z)</code>, this will not work because <code>N</code> will not be able to unify with <code>N2 is N - N1</code>. However, if I change this part to <code>N is N1 + N2</code>, this will still not work because <code>N2</code> is still not unified. If I change the whole predicate line to:</p>
  
  <pre><code>path(X, Y, N, [Z|T]) :- edge(X, Z, N1), path(Z, Y, N2, T), N is N1 + N2.
  </code></pre>
  
  <p>This will then run endlessly because the number of paths are possibly infinite because the graph may contain loops (which I want to try to keep it that way as a challenge).</p>
  
  <p>As for the <code>shortestpath/3</code> predicate, I cannot find all paths and check whether all the paths are longer because the number of paths may be infinite due to having a cycle. Instead, I tried to find any paths which have length between 0 and the given <code>N</code>; if no path exists, then this is definitely the shortest path.</p>
  
  <pre><code>countdown(N, N).
  countdown(N, X) :- N1 is N - 1, N1 &gt;= 0, countdown(N1, X).
  
  shortestpath(A, B, N) :- path(A, B, N), \+((countdown(N, N1), N &gt; N1, path(A, B, N1))).
  </code></pre>
  
  <p>However this doesn't address the <code>N</code> given as a variable (because the countdown function wouldn't work), let alone the <em>unique</em> constraint.</p>
  
  <p>So my question is, is there a way to make this question work or is it actually impossible to do so? If there is such a solution, please kindly provide it here (or if you think this is a "homework" question, please at least guide me in the correct direction).</p>
  
  <p><strong>Constraints:</strong></p>
  
  <ul>
  <li><p>I don't want to use any built-in predicates. Only 'simple' or 'core' predicates such as <code>\+</code>, <code>is</code>, <code>+</code>, for example. <code>var</code>, <code>nonvar</code>, <code>asserta</code> and similar predicates are also somewhat acceptable (since there is no alternative which achieves the same functionality).</p></li>
  <li><p>I want it to be as general as possible; that is, any arguments for the predicate should be able to give as a variable. (or at least have the last argument of <code>shortestpath/3</code>, which is the length of the shortest path, a variable).</p></li>
  </ul>
  
  <hr>
  
  <p><em>I have looked through the following questions already and it doesn't answers my situation:</em></p>
  
  <ul>
  <li><p><a href="https://stackoverflow.com/questions/10812108/find-the-shortest-path-between-two-nodes-in-a-graph-in-prolog">Find the shortest path between two nodes in a graph in Prolog</a> (Doesn't address weighted edges and also uses complex predicates (e.g. <code>path/4</code>).</p></li>
  <li><p><a href="https://stackoverflow.com/questions/2564058/search-all-paths-and-the-shortest-path-for-a-graph-prolog">search all paths and the shortest path for a graph - Prolog</a> (Doesn't address graphs with cycles).</p></li>
  <li><p><a href="https://stackoverflow.com/questions/41112132/find-the-shortest-path-between-two-nodes-in-a-graph-in-prolog-and-display-the">Find the shortest path between two nodes in a graph in (Prolog) and display the result as array</a> (Doesn't address weighted edges).</p></li>
  </ul>
  
  <p>Please feel free to point me to any other question that address my question.</p>