# Floyd-Warshall algorithm in Prolog

**URL:** <https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685>\
**Category:** General\
**Created:** [December 20, 2024, 5:46pm UTC](https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685 "2024-12-20T17:46:13Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 20, 2024, 5:46pm UTC](https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685/1 "2024-12-20T17:46:14Z")

</div>

[Floyd-Warshall](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) is a well known and simple algorithm for finding all the shortest paths in a graph through dynamic programming. Here is the pseudo-code:

```prolog
let dist be a |V| × |V| array, initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v) // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

```

I’d like an implementation in a Prolog sympathetic way: immutable, perhaps using tabling, whilst hopefully conserving the conciseness of the original.

Does anyone have any such code, or might you fancy a stab at it?

---

<div class="post-metadata">

**Author:** ![kwon-young](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/kwon-young/32/4841_2.png) [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)\
**Post date:** [December 20, 2024, 9:31pm UTC](https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685/2 "2024-12-20T21:31:19Z")

</div>

Hello,  
Here is my version using a list of list for a matrix with fully ground elements, meaning that you have to copy the matrix every time you do an update.  
I think this is kind of the worst implementation anyone can think of, therefore kind of a good baseline ? 🙂

It is immutable as requested but the conciseness is not quite as good as the original because of for loops, especially nested ones…

```prolog
floyd_warshall(V, Graph, M4) :-
   length(M1, V),
   maplist(length_(V), M1),
   maplist(maplist(=(inf)), M1),
   foldl(edges, Graph, M1, M2),
   numlist(1, V, Vertices),
   foldl(vertices, Vertices, M2, M3),
   transitive(Vertices, M3, M4).

edges((U1-V1)-W, M1, M2) :-
   replace(U1, V1, M1, _, W, M2).

vertices(I, M1, M2) :-
   replace(I, I, M1, _, 0, M2).

transitive(Vertices, M1, M2) :-
   foldl(transitive(Vertices), Vertices, M1, M2).
transitive(Vertices, K, M1, M2) :-
   foldl(transitive(Vertices, K), Vertices, M1, M2).
transitive(Vertices, K, I, M1, M2) :-
   foldl(transitive_(K, I), Vertices, M1, M2).

transitive_(K, I, J, M1, M2) :-
   replace(I, J, M1, IJ1, IJ2, M2),
   nth2d(I, K, M1, IK),
   nth2d(K, J, M1, KJ),
   IKJ is IK + KJ,
   ( IJ1 > IKJ
   -> IJ2 = IKJ
   ; IJ2 = IJ1
   ).

```

Here is a example query, (the graph comes from [wikipedia](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Example)):

```prolog
?- graph(G), gtrace, floyd_warshall(4, G, M).
G = [2-1-4, 2-3-3, 1-3- -2, 3-4-2, 4-2- -1],
M = [[0, -1, -2, 0], [4, 0, 2, 4], [5, 1, 0, 2], [3, -1, 1, 0]].

```

> **prolog code with graph fact and helper predicates**
>
> ```prolog
> graph([
> (2-1)-4,
> (2-3)-3,
> (1-3)-(-2),
> (3-4)-2,
> (4-2)-(-1)
> ]).
> 
> length_(Len, List) :-
> length(List, Len).
> 
> nth2d(I, J, M, V) :-
> nth1(I, M, Row),
> nth1(J, Row, V).
> 
> replace(I, L1, Old, New, L3) :-
> nth1(I, L1, Old, L2),
> nth1(I, L3, New, L2).
> 
> replace(I1, I2, M1, Old, New, M2) :-
> replace(I1, M1, Row1, Row2, M2),
> replace(I2, Row1, Old, New, Row2).
> 
> ```

PS: Seriously, why do you have to do this to me, you can’t expect me not to spend my holiday not optimizing this like I did with dijkstra 😭

---

<div class="post-metadata">

**Author:** ![kwon-young](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/kwon-young/32/4841_2.png) [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)\
**Post date:** [December 20, 2024, 9:33pm UTC](https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685/3 "2024-12-20T21:33:54Z")

</div>

By the way:

> [@emiruz](#):
>
> I’d like an implementation in a Prolog sympathetic way: **immutable**

Does using clpfd variables for tracking distances count as immutable ?

> [@emiruz](#):
>
> perhaps using tabling

I don’t think tabling will help here with the three nested for loops.

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [December 20, 2024, 9:58pm UTC](https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685/4 "2024-12-20T21:58:06Z")

</div>

_The Craft of Prolog_ by Richard O’Keefe, page 171 (except it says “Warshall’s algorithm” rather than “Floyd-Warshall algorithm”.  
And there’s a discussion of the problem starting at page 167.

---

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 21, 2024, 7:35am UTC](https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685/6 "2024-12-21T07:35:16Z")

</div>

Thanks @kwon-young, I suspect the algorithm may need some re-thinking to be Prolog friendly, if it is at all possible. Yours is a functional version of the imperative code, and roughly O(V^5) I think.

I like the DSL @anon95304481 but the actual code looks imperative, mutable and non-backtrackable.

@peter.ludemann its the transitive closure algorithm. It is given on page 5 [here](https://cs.winona.edu/lin/cs440/ch08-2.pdf). I think that the main difference is the min condition from above is replaced with a logical OR. O’Keefe accumulates results using a ordered set since the values are binary, otherwise it is similar to @kwon-young approach. I don’t think this works when distance is required because we cannot make the value of a member in a set implicit (e.g. if its in the set then true); there needs to be some kind of updating structure, or a reenvisioning of how the algorithm calculates.

---

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 21, 2024, 8:02am UTC](https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685/7 "2024-12-21T08:02:13Z")

</div>

To minimise the pain of Aoc 2024 Day 16 in Prolog, I suspect I’ll end up just biting the bullet and using nb\_setarg/3. I’m really loathed to implement Djisktra yet again.

---

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 21, 2024, 8:57am UTC](https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685/8 "2024-12-21T08:57:55Z")

</div>

So I’m thinking of keeping distance state a bit like this. Say I have N vertices:

```prolog
NN is N**2,
length(Dist0, NN),
maplist(=(10**5), Dist0),
Dist =.. [dist|Dist0].

```

I’ll pass `Dist` around. It can then be accessed using arg/3 or changed using setarg/3 or nb\_setarg/3 (which I expect is faster). Pretty horrible, but needs must.

---

<div class="post-metadata">

**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\
**Post date:** [December 21, 2024, 10:55am UTC](https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685/9 "2024-12-21T10:55:26Z")

</div>

> [@emiruz](#):
>
> ```prolog
> maplist(=(10**5), Dist0),
> 
> ```

Note that `10**5` is not evaluated. I’d consider using a variable as initial value.

> [@emiruz](#):
>
> Pretty horrible, but needs must.

Yes. It is probably as good as it can be in Prolog. My only other hope would be using mode directed tabling. Possibly you an tweak that to do what you want, but it will always be a lot more expensive.

---

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 21, 2024, 2:52pm UTC](https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685/12 "2024-12-21T14:52:40Z")

</div>

> [@anon95304481](#):
>
> Is this based on performance measure or elegancy of code?  
> The idea to have predicates implemented with [nb\_setarg/3](https://www.swi-prolog.org/pldoc/doc_for?object=nb_setarg/3)  
> and still have an innocent contract is not new.

Each to their own I suppose, but under those guises you might as well implement it in C.

---

<div class="post-metadata">

**Author:** ![emiruz](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/emiruz/32/4495_2.png) [@emiruz](https://swi-prolog.discourse.group/u/emiruz)\
**Post date:** [December 21, 2024, 3:11pm UTC](https://swi-prolog.discourse.group/t/floyd-warshall-algorithm-in-prolog/8685/14 "2024-12-21T15:11:08Z")

</div>

That rather depends on the SWI Prolog C API, but presumably it caters for that? Further, if memory is copied to Prolog at the end of the call then presumably all allocation can happen within the function. It largely depends on how the API works rather than whether its possible to free memory in an interop 🙂