Floyd-Warshall algorithm: Difference between revisions
Add Scala implementation
(Add Scala implementation) |
|||
(15 intermediate revisions by 6 users not shown) | |||
Line 31:
{{trans|Python}}
<
V rn = 0 .< n
V dist = rn.map(i -> [1'000'000] * @n)
Line 53:
print(‘#. -> #. #4 #.’.format(i + 1, j + 1, dist[i][j], path.map(p -> String(p + 1)).join(‘ -> ’)))
floyd_warshall(4, [(1, 3, -2), (2, 1, 4), (2, 3, 3), (3, 4, 2), (4, 2, -1)])</
{{out}}
Line 74:
=={{header|360 Assembly}}==
{{trans|Rexx}}
<
FLOYDWAR CSECT
USING FLOYDWAR,R13 base register
Line 149:
XDEC DS CL12
YREGS
END FLOYDWAR</
{{out}}
<pre>
Line 170:
<
-- Floyd-Warshall algorithm.
--
Line 352:
end;
end floyd_warshall_task;</
{{out}}
Line 370:
4 -> 2 -1.00000E+00 4 -> 2
4 -> 3 1.00000E+00 4 -> 2 -> 1 -> 3</pre>
=={{header|ALGOL 68}}==
{{Trans|Lua}}
<syntaxhighlight lang="algol68">
BEGIN # Floyd-Warshall algorithm - translated from the Lua sample #
OP FMT = ( REAL v )STRING:
BEGIN
STRING result := fixed( ABS v, 0, 15 );
IF result[ LWB result ] = "." THEN "0" +=: result FI;
WHILE result[ UPB result ] = "0" DO result := result[ : UPB result - 1 ] OD;
IF result[ UPB result ] = "." THEN result := result[ : UPB result - 1 ] FI;
IF v < 0 THEN "-" ELSE " " FI + result
END # FMT # ;
PROC print result = ( [,]REAL dist, [,]INT nxt )VOID:
BEGIN
print( ( "pair dist path", newline ) );
FOR i FROM 1 LWB nxt TO 1 UPB nxt DO
FOR j FROM 2 LWB nxt TO 2 UPB nxt DO
IF i /= j THEN
INT u := i + 1;
INT v = j + 1;
print( ( whole( u, 0 ), " -> ", whole( v, 0 ), " "
, FMT dist[ i, j ], " ", whole( u, 0 )
)
);
WHILE u := nxt[ u - 1, v - 1 ];
print( ( " -> " +whole( u, 0 ) ) );
u /= v
DO SKIP OD;
print( ( newline ) )
FI
OD
OD
END # print result # ;
PROC floyd warshall = ( [,]INT weights, INT num vertices )VOID:
BEGIN
REAL infinity = max real;
[ 0 : num vertices - 1, 0 : num vertices - 1 ]REAL dist;
FOR i FROM LWB dist TO 1 UPB dist DO
FOR j FROM 2 LWB dist TO 2 UPB dist DO
dist[ i, j ] := infinity
OD
OD;
FOR i FROM 1 LWB weights TO 1 UPB weights DO
# the weights array is one based #
[]INT w = weights[ i, : ];
dist[ w[ 1 ] - 1, w[ 2 ] - 1 ] := w[ 3 ]
OD;
[ 0 : num vertices - 1, 0 : num vertices - 1 ]INT nxt;
FOR i FROM LWB nxt TO 1 UPB nxt DO
FOR j FROM 2 LWB nxt TO 2 UPB nxt DO
nxt[ i, j ] := IF i /= j THEN j + 1 ELSE 0 FI
OD
OD;
FOR k FROM 2 LWB dist TO 2 UPB dist DO
FOR i FROM 1 LWB dist TO 1 UPB dist DO
FOR j FROM 2 LWB dist TO 2 UPB dist DO
IF dist[ i, k ] /= infinity AND dist[ k, j ] /= infinity THEN
IF dist[ i, k ] + dist[ k, j ] < dist[ i, j ] THEN
dist[ i, j ] := dist[ i, k ] + dist[ k, j ];
nxt[ i, j ] := nxt[ i, k ]
FI
FI
OD
OD
OD;
print result( dist, nxt )
END # floyd warshall # ;
[,]INT weights = ( ( 1, 3, -2 )
, ( 2, 1, 4 )
, ( 2, 3, 3 )
, ( 3, 4, 2 )
, ( 4, 2, -1 )
);
INT num vertices = 4;
floyd warshall( weights, num vertices )
END
</syntaxhighlight>
{{out}}
<pre>
pair dist path
1 -> 2 -1 1 -> 3 -> 4 -> 2
1 -> 3 -2 1 -> 3
1 -> 4 0 1 -> 3 -> 4
2 -> 1 4 2 -> 1
2 -> 3 2 2 -> 1 -> 3
2 -> 4 4 2 -> 1 -> 3 -> 4
3 -> 1 5 3 -> 4 -> 2 -> 1
3 -> 2 1 3 -> 4 -> 2
3 -> 4 2 3 -> 4
4 -> 1 3 4 -> 2 -> 1
4 -> 2 -1 4 -> 2
4 -> 3 1 4 -> 2 -> 1 -> 3
</pre>
=={{header|ATS}}==
Line 384 ⟶ 489:
<
Floyd-Warshall algorithm.
Line 676 ⟶ 781:
end
end</
{{out}}
Line 703 ⟶ 808:
<
Floyd-Warshall algorithm.
Line 1,245 ⟶ 1,350:
end
(*------------------------------------------------------------------*)</
{{out}}
Line 1,266 ⟶ 1,371:
=={{header|C}}==
Reads the graph from a file, prints out usage on incorrect invocation.
<syntaxhighlight lang="c">
#include<limits.h>
#include<stdlib.h>
Line 1,342 ⟶ 1,447:
return 0;
}
</syntaxhighlight>
Input file, first row specifies number of vertices and edges.
<pre>
Line 1,355 ⟶ 1,460:
<pre>
C:\rosettaCode>fwGraph.exe fwGraph.txt
pair dist path
1 -> 2 -1 1->3->4->2
1 -> 3 -2 1->3
1 -> 4 0 1->3->4
2 -> 1 4 2->1
2 -> 3 2 2->1->3
2 -> 4 4 2->1->3->4
3 -> 1 5 3->4->2->1
3 -> 2 1 3->4->2
3 -> 4 2 3->4
4 -> 1 3 4->2->1
4 -> 2 -1 4->2
4 -> 3 1 4->2->1->3
</pre>
==={{libheader|Gadget}}===
VERSION 2. Using Gadget, an a "C" library.
<syntaxhighlight lang="c">
#include <limits.h>
#include <gadget/gadget.h>
LIB_GADGET_START
/* algunos datos globales */
int vertices,edges;
/* algunos prototipos */
F_STAT DatosdeArchivo( const char *cFile);
int * CargaMatriz(int * mat, DS_ARRAY * mat_data, const char * cFile, F_STAT stat );
int * CargaGrafo(int * graph, DS_ARRAY * graph_data, const char *cFile);
void Floyd_Warshall(int * graph, DS_ARRAY graph_data);
/* bloque principal */
Main
if ( Arg_count != 2 ){
Msg_yellow("Modo de uso:\n ./floyd <archivo_de_vertices>\n");
Stop(1);
}
Get_arg_str (cFile,1);
Set_token_sep(' ');
Cls;
if(Exist_file(cFile)){
New array graph as int;
graph = CargaGrafo( pSDS(graph), cFile);
if(graph){
/* calcula Floyd-Warshall */
Print "Vertices=%d, edges=%d\n",vertices,edges;
Floyd_Warshall( SDS(graph) ); Prnl;
Free array graph;
}
}else{
Msg_redf("No existe el archivo %s",cFile);
}
Free secure cFile;
End
void Floyd_Warshall( RDS(int,graph) ){
Array processedVertices as int(vertices,vertices);
Fill array processWeights as int(vertices,vertices) with SHRT_MAX;
int i,j,k;
Range for processWeights [0:1:vertices, 0:1:vertices ];
Compute_for( processWeights, i,j,
$processedVertices[i,j] = (i!=j)?j+1:0;
)
#define VERT_ORIG 0
#define VERT_DEST 1
#define WEIGHT 2
Iterator up i [0:1:edges] {
$2processWeights[ $graph[i,VERT_ORIG]-1, $graph[i,VERT_DEST]-1 ] = $graph[i,WEIGHT];
}
Compute_for (processWeights,i,j,
Iterator up k [0:1:vertices] {
if( $processWeights[j,i] + $processWeights[i,k] < $processWeights[j,k] )
{
$processWeights[j,k] = $processWeights[j,i] + $processWeights[i,k];
$processedVertices[j,k] = $processedVertices[j,i];
}
} );
Print "pair dist path";
// ya existen rangos definios para "processWeights":
Compute_for(processWeights, i, j,
if(i!=j)
{
Print "\n%d -> %d %3d %5d", i+1, j+1, $processWeights[i,j], i+1;
int k = i+1;
do{
k = $processedVertices[k-1,j];
Print " -> %d", k;
}while(k!=j+1);
}
);
Free array processWeights, processedVertices;
}
F_STAT DatosdeArchivo( const char *cFile){
return Stat_file(cFile);
}
int * CargaMatriz( pRDS(int, mat), const char * cFile, F_STAT stat ){
return Load_matrix( SDS(mat), cFile, stat);
}
int * CargaGrafo( pRDS(int, graph), const char *cFile){
F_STAT dataFile = DatosdeArchivo(cFile);
if(dataFile.is_matrix){
Range ptr graph [0:1:dataFile.total_lines-1, 0:1:dataFile.max_tokens_per_line-1];
graph = CargaMatriz( SDS(graph), cFile, dataFile);
if( graph ){
/* obtengo vertices = 4 y edges = 5 */
edges = dataFile.total_lines;
Block( vertices, Range ptr graph [ 0:1:pRows(graph), 0:1:1 ];
DS_MAXMIN maxNode = Max_array( SDS(graph) );
Out_int( $graph[maxNode.local] ) );
}else{
Msg_redf("Archivo \"%s\" no ha podido ser cargado",cFile);
}
}else{
Msg_redf("Archivo \"%s\" no es cuadrado",cFile);
}
return graph;
}
</syntaxhighlight>
{{out}}
Archivo fuente: floyd_data.txt
<pre>
1 3 -2
3 4 2
4 2 -1
2 1 4
2 3 3
</pre>
Salida:
<pre>
$ ./floydWarshall floyd_data.txt
Vertices=4, edges=5
pair dist path
1 -> 2 -1 1->3->4->2
Line 1,372 ⟶ 1,632:
=={{header|C sharp|C#}}==
{{trans|Java}}
<
namespace FloydWarshallAlgorithm {
Line 1,436 ⟶ 1,696:
}
}
}</
=={{header|C++}}==
<
#include <vector>
#include <sstream>
Line 1,512 ⟶ 1,772:
std::cin.get();
return 0;
}</
{{out}}
Line 1,528 ⟶ 1,788:
(4 -> 2, -1, 4 -> 2)
(4 -> 3, 1, 4 -> 2 -> 1 -> 3)</pre>
=={{header|Common Lisp}}==
{{trans|Scheme}}
I have wrapped the Common Lisp program in a [https://roswell.github.io/ Roswell] script.
Notice how in Common Lisp you have to specially quote the name of a function to call that function as an argument, whereas in Scheme no such thing is necessary. (In fact, a Scheme procedure does not really have a name; you are giving the name of a variable that holds the procedure.)
"Looping" (or tail recursion) is done differently, although it is common for a Common Lisp-like '''loop''' macro to be available in Scheme. A Common Lisp-like '''format''' also often is available.
<syntaxhighlight lang="lisp">#!/bin/sh
#|-*- mode:lisp -*-|#
#|
exec ros -Q -- $0 "$@"
|#
(progn ;;init forms
(ros:ensure-asdf)
#+quicklisp(ql:quickload '() :silent t)
)
(defpackage :ros.script.floyd-warshall.3861181636
(:use :cl))
(in-package :ros.script.floyd-warshall.3861181636)
;;;
;;; Floyd-Warshall algorithm.
;;;
;;; See https://en.wikipedia.org/w/index.php?title=Floyd%E2%80%93Warshall_algorithm&oldid=1082310013
;;;
;;; Translated from the Scheme. Small improvements (or what might be
;;; considered improvements), and some type specialization, have been
;;; added.
;;;
;;;-------------------------------------------------------------------
;;;
;;; A square array will be represented by an ordinary Common Lisp
;;; array, but accessed through our own functions (which look similar
;;; to, although not identical to, the corresponding Scheme
;;; functions).
;;;
;;; Square arrays are indexed *starting at one*.
;;;
(defun make-arr (n &key (element-type t) initial-element)
(make-array (list n n) :element-type element-type
:initial-element initial-element))
(defun arr-set (arr i j x)
(setf (aref arr (- i 1) (- j 1)) x))
(defun arr-ref (arr i j)
(aref arr (- i 1) (- j 1)))
;;;-------------------------------------------------------------------
;;;
;;; Floyd-Warshall.
;;;
;;; Input is a list of length-3 lists representing edges; each entry
;;; is:
;;;
;;; (start-vertex edge-weight end-vertex)
;;;
;;; where vertex identifiers are integers from 1 .. n.
;;;
;;; A difference from the Scheme implementation is that here we do not
;;; assume the floating point supports "infinities". In the Scheme we
;;; did, because in R7RS small there is support for such infinities
;;; (although the standard does not *require* them). Also because
;;; alternatives were not yet apparent to this author. :)
;;;
(defvar *floatpt* 'single-float)
(defconstant nil-vertex 0)
(defun floyd-warshall (edges)
(let* ((n
;; Set n to the maximum vertex number. By design, n also
;; equals the number of vertices.
(max (apply #'max (mapcar #'car edges))
(apply #'max (mapcar #'caddr edges))))
(distance
;; The distances are initialized to a purely arbitrary
;; value. An entry in the "distance" array is meaningful
;; *only* if the corresponding entry in "next-vertex" is
;; not the nil-vertex.
(make-arr n :element-type *floatpt*
:initial-element (coerce 12345 *floatpt*)))
(next-vertex
;; Unless later set otherwise, an entry in "next-vertex"
;; will be the nil-vertex.
(make-arr n :element-type 'fixnum
:initial-element nil-vertex)))
(defun dist (p q) (arr-ref distance p q))
(defun next (p q) (arr-ref next-vertex p q))
(defun set-dist (p q x) (arr-set distance p q x))
(defun set-next (p q x) (arr-set next-vertex p q x))
(defun nilnext (p q) (= (next p q) nil-vertex))
;; Initialize "distance" and "next-vertex".
(loop for edge in edges
do (let ((u (car edge))
(weight (cadr edge))
(v (caddr edge)))
(set-dist u v weight)
(set-next u v v)))
(loop for v from 1 to n
do (progn
;; The distance from a vertex to itself = 0.0.
(set-dist v v (coerce 0 *floatpt*))
(set-next v v v)))
;; Perform the algorithm.
(loop
for k from 1 to n
do (loop
for i from 1 to n
do (loop
for j from 1 to n
do (and (not (nilnext i k))
(not (nilnext k j))
(let* ((dist-ikj (+ (dist i k) (dist k j))))
(when (or (nilnext i j)
(< dist-ikj (dist i j)))
(set-dist i j dist-ikj)
(set-next i j (next i k))))))))
;; Return the results.
(values n distance next-vertex)))
;;;-------------------------------------------------------------------
;;;
;;; Path reconstruction from the "next-vertex" array.
;;;
;;; The return value is a list of vertices.
;;;
(defun find-path (next-vertex u v)
(if (= (arr-ref next-vertex u v) nil-vertex)
(list)
(cons u (let ((i u))
(loop while (/= i v)
do (setf i (arr-ref next-vertex i v))
collect i)))))
;;;-------------------------------------------------------------------
(defun directed-vertex-list-to-string (lst)
(if (not lst)
""
(let ((s (write-to-string (car lst))))
(loop for u in (cdr lst)
do (setf s (concatenate 'string s " -> "
(write-to-string u))))
s)))
;;;-------------------------------------------------------------------
(defun main (&rest argv)
(declare (ignorable argv))
(let ((example-graph
(mapcar (lambda (x) (list (coerce (car x) 'fixnum)
(coerce (cadr x) *floatpt*)
(coerce (caddr x) 'fixnum)))
'((1 -2 3)
(3 2 4)
(4 -1 2)
(2 4 1)
(2 3 3)))))
(multiple-value-bind (n distance next-vertex)
(floyd-warshall example-graph)
(princ " pair distance path")
(terpri)
(princ "-------------------------------------")
(terpri)
(loop
for u from 1 to n
do (loop
for v from 1 to n
do (unless (= u v)
(format
t " ~A ~7@A ~A~%"
(directed-vertex-list-to-string (list u v))
(if (= (arr-ref next-vertex u v) nil-vertex)
" no path"
(write-to-string (arr-ref distance u v)))
(directed-vertex-list-to-string
(find-path next-vertex u v)))))))))
;;;-------------------------------------------------------------------
;;; vim: set ft=lisp lisp:</syntaxhighlight>
{{out}}
<pre>$ ./floyd-warshall.ros
pair distance path
-------------------------------------
1 -> 2 -1.0 1 -> 3 -> 4 -> 2
1 -> 3 -2.0 1 -> 3
1 -> 4 0.0 1 -> 3 -> 4
2 -> 1 4.0 2 -> 1
2 -> 3 2.0 2 -> 1 -> 3
2 -> 4 4.0 2 -> 1 -> 3 -> 4
3 -> 1 5.0 3 -> 4 -> 2 -> 1
3 -> 2 1.0 3 -> 4 -> 2
3 -> 4 2.0 3 -> 4
4 -> 1 3.0 4 -> 2 -> 1
4 -> 2 -1.0 4 -> 2
4 -> 3 1.0 4 -> 2 -> 1 -> 3</pre>
=={{header|D}}==
{{trans|Java}}
<
void main() {
Line 1,600 ⟶ 2,075:
}
}
}</
{{out}}
Line 1,619 ⟶ 2,094:
=={{header|EchoLisp}}==
Transcription of the Floyd-Warshall algorithm, with best path computation.
<
(lib 'matrix)
Line 1,661 ⟶ 2,136:
(array-print dist) ;; show init distances
(floyd-with-path n dist next))
</syntaxhighlight>
{{out}}
<pre>
Line 1,700 ⟶ 2,175:
=={{header|Elixir}}==
<
def main(n, edge) do
{dist, next} = setup(n, edge)
Line 1,743 ⟶ 2,218:
edge = [{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}]
Floyd_Warshall.main(4, edge)</
{{out}}
Line 1,764 ⟶ 2,239:
=={{header|F_Sharp|F#}}==
===Floyd's algorithm===
<
//Floyd's algorithm: Nigel Galloway August 5th 2018
let Floyd (n:'a[]) (g:Map<('a*'a),int>)= //nodes graph(Map of adjacency list)
Line 1,780 ⟶ 2,255:
|_->yield None}
yield! fN x y |> Seq.choose id; yield y}))
</syntaxhighlight>
===The Task===
<
let fW=Map[((1,3),-2);((3,4),2);((4,2),-1);((2,1),4);((2,3),3)]
let N,G=Floyd [|1..4|] fW
List.allPairs [1..4] [1..4]|>List.filter(fun (n,g)->n<>g)|>List.iter(fun (n,g)->printfn "%d->%d %d %A" n g N.[(n,g)] (n::(List.ofSeq (G n g))))
</syntaxhighlight>
{{out}}
<pre>
Line 1,809 ⟶ 2,284:
<
use, intrinsic :: ieee_arithmetic
Line 1,961 ⟶ 2,436:
end do
end program floyd_warshall_task</
{{out}}
Line 1,982 ⟶ 2,457:
=={{header|FreeBASIC}}==
{{trans|Java}}
<
Const POSITIVE_INFINITY As Double = 1.0/0.0
Line 2,043 ⟶ 2,518:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 2,063 ⟶ 2,538:
=={{header|Go}}==
<
import (
Line 2,175 ⟶ 2,650:
}
}
}</
{{out}}
<pre>
Line 2,195 ⟶ 2,670:
=={{header|Groovy}}==
{{trans|Java}}
<
static void main(String[] args) {
int[][] weights = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]
Line 2,255 ⟶ 2,730:
}
}
}</
{{out}}
<pre>pair dist path
Line 2,274 ⟶ 2,749:
Necessary imports
<
import Data.List (union)
import Data.Map hiding (foldr, union)
import Data.Maybe (fromJust, isJust)
import Data.Semigroup
import Prelude hiding (lookup, filter)</
First we define a general datatype to represent the shortest path. Type <code>a</code> represents a distance. It could be a number, in case of weighted graph or boolean value for just a directed graph. Type <code>b</code> goes for vertice labels (integers, chars, strings...)
<
deriving Show</
Next we note that shortest paths form a semigroup with following "addition" rule:
<
a <> b = case distance a `compare` distance b of
GT -> b
LT -> a
EQ -> a { path = path a `union` path b }</
It finds minimal path by <code>distance</code>, and in case of equal distances joins both paths. We will lift this semigroup to monoid using <code>Maybe</code> wrapper.
Line 2,299 ⟶ 2,774:
Now we are ready to define the main part of the Floyd-Warshall algorithm, which processes properly prepared distance table <code>dist</code> for given list of vertices <code>v</code>:
<
where
innerCycle k dist = (newDist <$> v <*> v) `setTo` dist
Line 2,308 ⟶ 2,783:
return $ Shortest (distance a <> distance b) (path a))
setTo = unionWith (<>) . fromList</
The <code>floydWarshall</code> produces only first steps of shortest paths. Whole paths are build by following function:
<
where
buildPath (i,j)
Line 2,318 ⟶ 2,793:
| otherwise = do k <- path $ fromJust $ lookup (i,j) d
p <- buildPath (k,j)
[i : p]</
All pre- and postprocessing is done by the main function <code>findMinDistances</code>:
<
let weights = mapWithKey (\(_,j) w -> Shortest w [j]) g
trivial = fromList [ ((i,i), Shortest mempty []) | i <- v ]
clean d = fromJust <$> filter isJust (d \\ trivial)
in buildPaths $ clean $ floydWarshall v (weights <> trivial)</
'''Examples''':
The sample graph:
<
,((2,3), 3)
,((1,3), -2)
,((3,4), 2)
,((4,2), -1)]</
the helper function
<
{{Out}}
Line 2,387 ⟶ 2,862:
Graph labeled by chars:
<
,(('A','D'), -1)
,(('S','E'), 2)
,(('D','E'), 4)]</
<pre>λ> showShortestPaths "ASDE" (Sum <$> g2)
Line 2,404 ⟶ 2,879:
<
# Floyd-Warshall algorithm.
#
Line 2,520 ⟶ 2,995:
every e := !edges do m := max (m, e[1], e[3])
return m
end</
{{out}}
Line 2,541 ⟶ 3,016:
=={{header|J}}==
<
for_j. i.#y do.
y=. y <. j ({"1 +/ {) y
end.
)</
Alternate implementation (same behavior):
<syntaxhighlight lang=J>floyd=: ]F..(]<.{"1+/{) i.@#</syntaxhighlight>
Example use:
<
0 _ _2 _ NB. 1->3 costs _2
4 0 3 _ NB. 2->1 costs 4; 2->3 costs 3
Line 2,560 ⟶ 3,039:
4 0 2 4
5 1 0 2
3 _1 1 0</
The graph matrix holds the costs of each directed node. Row index corresponds to starting node. Column index corresponds to ending node. Unconnected nodes have infinite cost.
Line 2,570 ⟶ 3,049:
This draft task currently asks for path reconstruction, which is a different (related) algorithm:
<
n=. ($y)$_(I._=,y)},($$i.@#)y
for_j. i.#y do.
Line 2,602 ⟶ 3,081:
end.
i.0 0
)</
Draft output:
<
pair dist path
1->2 _1 1->3->4->2
Line 2,619 ⟶ 3,098:
4->1 3 4->2->1
4->2 _1 4->2
4->3 1 4->2->1->3</
=={{header|Java}}==
<
import java.util.Arrays;
Line 2,679 ⟶ 3,158:
}
}
}</
<pre>pair dist path
1 -> 2 -1 1 -> 3 -> 4 -> 2
Line 2,695 ⟶ 3,174:
=={{header|JavaScript}}==
Using output code translated from the Lua sample.
<syntaxhighlight lang
let numVertices = 4;
let weights = [ [ 1, 3, -2 ], [ 2, 1, 4 ], [ 2, 3, 3 ], [ 3, 4, 2 ], [ 4, 2, -1 ] ];
let graph = [];
for (let i = 0; i < numVertices; ++i) {
graph.push([]);
for (let j = 0; j <
graph[i].push(i == j ? 0 : 9999999);
}
for (let i =
let w = weights[i];
graph[w[0] - 1][w[1] - 1] = w[2];
}
let nxt = [];
nxt.push([]);
for (let j =
}
for (let k = 0; k < numVertices; ++k) {
for (let i = 0; i < numVertices; ++i) {
for (let j = 0; j < numVertices; ++j) {
if (graph[i][j] > graph[i][k] + graph[k][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
nxt[i][j] = nxt[i][k];
}
}
}
}
console.log(
for (let i = 0; i < numVertices; ++i) {
for (let j = 0; j < numVertices; ++j) {
if (i != j) {
let u = i + 1;
let v = j + 1;
let path = u + " -> " + v + " " + graph[i][j].toString().padStart(2) + " " + u;
do {
u = nxt[u - 1][v - 1];
path = path + " -> " + u;
} while (u != v);
console.log(path)
}
}
}
</syntaxhighlight>
{{out}}
<pre>
pair dist path
1 -> 2 -1 1 -> 3 -> 4 -> 2
1 -> 3 -2 1 -> 3
1 -> 4 0 1 -> 3 -> 4
2 -> 1 4 2 -> 1
2 -> 3 2 2 -> 1 -> 3
2 -> 4 4 2 -> 1 -> 3 -> 4
3 -> 1 5 3 -> 4 -> 2 -> 1
3 -> 2 1 3 -> 4 -> 2
3 -> 4 2 3 -> 4
4 -> 1 3 4 -> 2 -> 1
4 -> 2 -1 4 -> 2
4 -> 3 1 4 -> 2 -> 1 -> 3
</pre>
=={{header|jq}}==
{{works with|jq|1.5}}
In this section, we represent the graph by a JSON object giving the weights: if u and v are the (string) labels of two nodes connected with an arrow from u to v, then .[u][v] is the associated weight:
<syntaxhighlight lang="jq">
def weights: {
"1": {"3": -2},
Line 2,727 ⟶ 3,252:
"3": {"4": 2},
"4": {"2": -1}
};</
The algorithm given here is a direct implementation of the definitional algorithm:
<
. as $weights
| keys_unsorted as $nodes
Line 2,750 ⟶ 3,275:
weights | fwi</
{{out}}
<pre>{
Line 2,781 ⟶ 3,306:
=={{header|Julia}}==
{{trans|Java}}
<
# v0.6
Line 2,818 ⟶ 3,343:
end
floydwarshall([1 3 -2; 2 1 4; 2 3 3; 3 4 2; 4 2 -1], 4)</
=={{header|Kotlin}}==
{{trans|Java}}
<
object FloydWarshall {
Line 2,879 ⟶ 3,404:
val nVertices = 4
FloydWarshall.doCalcs(weights, nVertices)
}</
{{out}}
Line 2,900 ⟶ 3,425:
=={{header|Lua}}==
{{trans|D}}
<
print("pair dist path")
for i=0, #nxt do
Line 2,964 ⟶ 3,489:
}
numVertices = 4
floydWarshall(weights, numVertices)</
{{out}}
<pre>pair dist path
Line 2,982 ⟶ 3,507:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
4 \[DirectedEdge] 2, 2 \[DirectedEdge] 1, 2 \[DirectedEdge] 3},
EdgeWeight -> {(1 \[DirectedEdge] 3) -> -2, (3 \[DirectedEdge] 4) ->
Line 2,993 ⟶ 3,518:
Catenate[
Table[{vl[[i]], vl[[j]], dm[[i, j]]}, {i, Length[vl]}, {j,
Length[vl]}]], {x_, x_, _}]]]</
{{out}}
<pre>1 2 -1.
Line 3,008 ⟶ 3,533:
4 3 1.</pre>
=={{header|Mercury}}==
{{trans|Scheme}}
{{works with|Mercury|20.06.1}}
<syntaxhighlight lang="mercury">:- module floyd_warshall_task.
:- interface.
:- import_module io.
:- pred main(io, io).
:- mode main(di, uo) is det.
:- implementation.
:- import_module float.
:- import_module int.
:- import_module list.
:- import_module string.
:- import_module version_array2d.
%%%-------------------------------------------------------------------
%% Square arrays with 1-based indexing.
:- func arr_init(int, T) = version_array2d(T).
arr_init(N, Fill) = version_array2d.init(N, N, Fill).
:- func arr_get(version_array2d(T), int, int) = T.
arr_get(Arr, I, J) = Elem :-
I1 = I - 1,
J1 = J - 1,
Elem = Arr^elem(I1, J1).
:- func arr_set(version_array2d(T), int, int, T) = version_array2d(T).
arr_set(Arr0, I, J, Elem) = Arr :-
I1 = I - 1,
J1 = J - 1,
Arr = (Arr0^elem(I1, J1) := Elem).
%%%-------------------------------------------------------------------
:- func find_max_vertex(list({int, float, int})) = int.
find_max_vertex(Edges) = find_max_vertex_(Edges, 0).
:- func find_max_vertex_(list({int, float, int}), int) = int.
find_max_vertex_([], MaxVertex0) = MaxVertex0.
find_max_vertex_([{U, _, V} | Tail], MaxVertex0) = MaxVertex :-
MaxVertex = find_max_vertex_(Tail, max(max(MaxVertex0, U), V)).
%%%-------------------------------------------------------------------
:- func arbitrary_float = float.
arbitrary_float = (12345.0).
:- func nil_vertex = int.
nil_vertex = 0.
:- func floyd_warshall(list({int, float, int})) =
{int, version_array2d(float), version_array2d(int)}.
floyd_warshall(Edges) = {N, Dist, Next} :-
N = find_max_vertex(Edges),
Dist0 = arr_init(N, arbitrary_float),
Next0 = arr_init(N, nil_vertex),
(if (N = 0) then (Dist = Dist0,
Next = Next0)
else ({Dist1, Next1} = floyd_warshall_initialize(Edges, N,
Dist0, Next0),
{Dist, Next} = floyd_warshall_loop_k(N, 1, Dist1, Next1))).
:- func floyd_warshall_initialize(list({int, float, int}),
int,
version_array2d(float),
version_array2d(int)) =
{version_array2d(float), version_array2d(int)}.
floyd_warshall_initialize(Edges, N, Dist0, Next0) = {Dist1, Next1} :-
floyd_warshall_read_edges(Edges, Dist0, Next0) = {D1, X1},
floyd_warshall_diagonals(N, 1, D1, X1) = {Dist1, Next1}.
:- func floyd_warshall_read_edges(list({int, float, int}),
version_array2d(float),
version_array2d(int)) =
{version_array2d(float), version_array2d(int)}.
floyd_warshall_read_edges([], Dist0, Next0) = {Dist0, Next0}.
floyd_warshall_read_edges([{U, Weight, V} | Tail],
Dist0, Next0) = {Dist1, Next1} :-
D1 = arr_set(Dist0, U, V, Weight),
X1 = arr_set(Next0, U, V, V),
floyd_warshall_read_edges(Tail, D1, X1) = {Dist1, Next1}.
:- func floyd_warshall_diagonals(int, int,
version_array2d(float),
version_array2d(int)) =
{version_array2d(float), version_array2d(int)}.
floyd_warshall_diagonals(N, I, Dist0, Next0) = {Dist1, Next1} :-
N1 = N + 1,
(if (I = N1) then (Dist1 = Dist0,
Next1 = Next0)
else (
%% The distance from a vertex to itself = 0.0.
D1 = arr_set(Dist0, I, I, 0.0),
X1 = arr_set(Next0, I, I, I),
I1 = I + 1,
floyd_warshall_diagonals(N, I1, D1, X1) = {Dist1, Next1})).
:- func floyd_warshall_loop_k(int, int,
version_array2d(float),
version_array2d(int)) =
{version_array2d(float), version_array2d(int)}.
floyd_warshall_loop_k(N, K, Dist0, Next0) = {Dist1, Next1} :-
N1 = N + 1,
(if (K = N1) then (Dist1 = Dist0,
Next1 = Next0)
else ({D1, X1} = floyd_warshall_loop_i(N, K, 1, Dist0, Next0),
K1 = K + 1,
{Dist1, Next1} = floyd_warshall_loop_k(N, K1, D1, X1))).
:- func floyd_warshall_loop_i(int, int, int,
version_array2d(float),
version_array2d(int)) =
{version_array2d(float), version_array2d(int)}.
floyd_warshall_loop_i(N, K, I, Dist0, Next0) = {Dist1, Next1} :-
N1 = N + 1,
(if (I = N1) then (Dist1 = Dist0,
Next1 = Next0)
else ({D1, X1} = floyd_warshall_loop_j(N, K, I, 1, Dist0, Next0),
I1 = I + 1,
{Dist1, Next1} = floyd_warshall_loop_i(N, K, I1, D1, X1))).
:- func floyd_warshall_loop_j(int, int, int, int,
version_array2d(float),
version_array2d(int)) =
{version_array2d(float), version_array2d(int)}.
floyd_warshall_loop_j(N, K, I, J, Dist0, Next0) = {Dist1, Next1} :-
J1 = J + 1,
N1 = N + 1,
(if (J = N1) then (Dist1 = Dist0,
Next1 = Next0)
else (if ((arr_get(Next0, I, K) = nil_vertex);
(arr_get(Next0, K, J) = nil_vertex))
then ({Dist1, Next1} =
floyd_warshall_loop_j(N, K, I, J1, Dist0, Next0))
else (Dist_ikj = arr_get(Dist0, I, K) + arr_get(Dist0, K, J),
(if (arr_get(Next0, I, J) = nil_vertex;
Dist_ikj < arr_get(Dist0, I, J))
then (D1 = arr_set(Dist0, I, J, Dist_ikj),
X1 = arr_set(Next0, I, J, arr_get(Next0, I, K)),
{Dist1, Next1} =
floyd_warshall_loop_j(N, K, I, J1, D1, X1))
else ({Dist1, Next1} =
floyd_warshall_loop_j(N, K, I, J1,
Dist0, Next0)))))).
%%%-------------------------------------------------------------------
:- func path_string(version_array2d(int), int, int) = string.
path_string(Next, U, V) = S :-
if (arr_get(Next, U, V) = nil_vertex) then S = ""
else S = path_string_(Next, U, V, int_to_string(U)).
:- func path_string_(version_array2d(int), int, int, string) = string.
path_string_(Next, U, V, S0) = S :-
(if (U = V) then (S = S0)
else (U1 = arr_get(Next, U, V),
S1 = append(append(S0, " -> "), int_to_string(U1)),
path_string_(Next, U1, V, S1) = S)).
%%%-------------------------------------------------------------------
main(!IO) :-
Example_graph = [{1, -2.0, 3},
{3, 2.0, 4},
{4, -1.0, 2},
{2, 4.0, 1},
{2, 3.0, 3}],
{N, Dist, Next} = floyd_warshall(Example_graph),
format(" pair distance path\n", [], !IO),
format("-------------------------------------\n", [], !IO),
main_loop_u(N, 1, Dist, Next, !IO).
:- pred main_loop_u(int, int,
version_array2d(float),
version_array2d(int),
io, io).
:- mode main_loop_u(in, in, in, in, di, uo) is det.
main_loop_u(N, U, Dist, Next, !IO) :-
N1 = N + 1,
(if (U = N1) then true
else (main_loop_v(N, U, 1, Dist, Next, !IO),
U1 = U + 1,
main_loop_u(N, U1, Dist, Next, !IO))).
:- pred main_loop_v(int, int, int,
version_array2d(float),
version_array2d(int),
io, io).
:- mode main_loop_v(in, in, in, in, in, di, uo) is det.
main_loop_v(N, U, V, Dist, Next, !IO) :-
V1 = V + 1,
N1 = N + 1,
(if (V = N1) then true
else if (U = V) then main_loop_v(N, U, V1, Dist, Next, !IO)
else (format(" %d -> %d %4.1f %s\n",
[i(U), i(V), f(arr_get(Dist, U, V)),
s(path_string(Next, U, V))],
!IO),
main_loop_v(N, U, V1, Dist, Next, !IO))).
%%%-------------------------------------------------------------------
%%% local variables:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</syntaxhighlight>
{{out}}
<pre>$ mmc floyd_warshall_task.m && ./floyd_warshall_task
pair distance path
-------------------------------------
1 -> 2 -1.0 1 -> 3 -> 4 -> 2
1 -> 3 -2.0 1 -> 3
1 -> 4 0.0 1 -> 3 -> 4
2 -> 1 4.0 2 -> 1
2 -> 3 2.0 2 -> 1 -> 3
2 -> 4 4.0 2 -> 1 -> 3 -> 4
3 -> 1 5.0 3 -> 4 -> 2 -> 1
3 -> 2 1.0 3 -> 4 -> 2
3 -> 4 2.0 3 -> 4
4 -> 1 3.0 4 -> 2 -> 1
4 -> 2 -1.0 4 -> 2
4 -> 3 1.0 4 -> 2 -> 1 -> 3</pre>
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM SpecialReals IMPORT Infinity;
Line 3,094 ⟶ 3,848:
ReadChar
END FloydWarshall.</
=={{header|Nim}}==
{{trans|D}}
<
type
Line 3,152 ⟶ 3,906:
let numVertices = 4
floydWarshall(weights, numVertices)</
{{out}}
Line 3,177 ⟶ 3,931:
Certainly there are better ways to write an Object Icon implementation (for example, using a class instead of '''record'''), but this helps show that most of the classical dialect is still there.
<
# Floyd-Warshall algorithm.
#
Line 3,293 ⟶ 4,047:
every e := !edges do m := max (m, e[1], e[3])
return m
end</
{{out}}
Line 3,318 ⟶ 4,072:
This implementation was written by referring frequently to [[#ATS|the ATS]], but differs from it considerably. For example, it assumes IEEE floating point, whereas the ATS purposely avoided that assumption. However, the "square array" and "edge" types are very similar to the ATS equivalents.
<
Floyd-Warshall algorithm.
Line 3,527 ⟶ 4,281:
done
done
;;</
{{out}}
Line 3,547 ⟶ 4,301:
=={{header|Perl}}==
<
my $edges = shift;
my (@dist, @seq);
Line 3,596 ⟶ 4,350:
my $graph = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]];
FloydWarshall($graph);</
{{out}}
<pre>pair dist path
Line 3,614 ⟶ 4,368:
=={{header|Phix}}==
Direct translation of the wikipedia pseudocode
<!--<
<span style="color: #008080;">constant</span> <span style="color: #000000;">inf</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e300</span><span style="color: #0000FF;">*</span><span style="color: #000000;">1e300</span>
Line 3,662 ⟶ 4,416:
<span style="color: #008080;">constant</span> <span style="color: #000000;">weights</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span>
<span style="color: #000000;">FloydWarshall</span><span style="color: #0000FF;">(</span><span style="color: #000000;">V</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weights</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 3,681 ⟶ 4,435:
=={{header|PHP}}==
<
$graph = array();
for ($i = 0; $i < 10; ++$i) {
Line 3,703 ⟶ 4,457:
print_r($graph);
?></
=={{header|Prolog}}==
Works with SWI-Prolog as of Jan 2019
<
path(List, To, From, [From], W) :-
Line 3,733 ⟶ 4,487:
find_path(D, From, To, Path, Weight),(
atomic_list_concat(Path, ' -> ', PPath),
format('~p -> ~p\t ~p\t~w~n', [From, To, Weight, PPath]))).</
{{output}}
<pre>?- print_all_paths.
Line 3,755 ⟶ 4,509:
=={{header|Python}}==
{{trans|Ruby}}
<
from itertools import product
Line 3,783 ⟶ 4,537:
if __name__ == '__main__':
floyd_warshall(4, [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]])</
{{output}}
Line 3,802 ⟶ 4,556:
=={{header|Racket}}==
{{trans|EchoLisp}}
<
(require math/array)
Line 3,877 ⟶ 4,631:
(mdist dist+ 1 3)
(path next+ 7 6)
(path next+ 6 7))</
{{out}}
Line 3,922 ⟶ 4,676:
{{trans|Ruby}}
<syntaxhighlight lang="raku"
my @dist = [0, |(Inf xx $n-1)], *.Array.rotate(-1) … !*[*-1];
my @next = [0 xx $n] xx $n;
Line 3,948 ⟶ 4,702:
}
Floyd-Warshall(4, [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]);</
{{out}}
<pre> Pair Distance Path
Line 3,972 ⟶ 4,726:
<
# Floyd-Warshall algorithm.
#
Line 4,225 ⟶ 4,979:
write (* , '(1000A1)') (str(j:j), j = 1, trimr (str))
}
end</
{{out}}
Line 4,272 ⟶ 5,026:
=={{header|REXX}}==
<
v= 4 /*███ {1} ███*/ /*number of vertices in weighted graph.*/
@.= 99999999 /*███ 4 / \ -2 ███*/ /*the default distance (edge weight). */
Line 4,297 ⟶ 5,051:
say $ center(f '───►' t, w) right(@.f.t, w % 2)
end /*t*/ /* [↑] the distance between 2 vertices*/
end /*f*/ /*stick a fork in it, we're all done. */</
{{out|output|text= when using the default inputs:}}
<pre>
Line 4,318 ⟶ 5,072:
=={{header|Ruby}}==
<
dist = Array.new(n){|i| Array.new(n){|j| i==j ? 0 : Float::INFINITY}}
nxt = Array.new(n){Array.new(n)}
Line 4,352 ⟶ 5,106:
n = 4
edge = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]
floyd_warshall(n, edge)</
{{out}}
Line 4,377 ⟶ 5,131:
and it requires no special value for infinity.
<
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
Line 4,590 ⟶ 5,344:
print_results(&weights, paths.as_ref(), |index| index + 1);
}
</syntaxhighlight>
{{out}}
Line 4,606 ⟶ 5,360:
4 -> 2: -1 4 -> 2
4 -> 3: 1 4 -> 2 -> 1 -> 3
</pre>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
import java.lang.String.format;
object FloydWarshall extends App {
val weights = Array(Array(1, 3, -2), Array(2, 1, 4), Array(2, 3, 3), Array(3, 4, 2), Array(4, 2, -1))
val numVertices = 4
floydWarshall(weights, numVertices)
def floydWarshall(weights: Array[Array[Int]], numVertices: Int): Unit = {
val dist = Array.fill(numVertices, numVertices)(Double.PositiveInfinity)
for (w <- weights)
dist(w(0) - 1)(w(1) - 1) = w(2)
val next = Array.ofDim[Int](numVertices, numVertices)
for (i <- 0 until numVertices; j <- 0 until numVertices if i != j)
next(i)(j) = j + 1
for {
k <- 0 until numVertices
i <- 0 until numVertices
j <- 0 until numVertices
if dist(i)(k) + dist(k)(j) < dist(i)(j)
} {
dist(i)(j) = dist(i)(k) + dist(k)(j)
next(i)(j) = next(i)(k)
}
printResult(dist, next)
}
def printResult(dist: Array[Array[Double]], next: Array[Array[Int]]): Unit = {
println("pair dist path")
for {
i <- 0 until next.length
j <- 0 until next.length if i != j
} {
var u = i + 1
val v = j + 1
var path = format("%d -> %d %2d %s", u, v,
(dist(i)(j)).toInt, u);
while (u != v) {
u = next(u - 1)(v - 1)
path += s" -> $u"
}
println(path)
}
}
}
</syntaxhighlight>
{{out}}
<pre>
pair dist path
1 -> 2 -1 1 -> 3 -> 4 -> 2
1 -> 3 -2 1 -> 3
1 -> 4 0 1 -> 3 -> 4
2 -> 1 4 2 -> 1
2 -> 3 2 2 -> 1 -> 3
2 -> 4 4 2 -> 1 -> 3 -> 4
3 -> 1 5 3 -> 4 -> 2 -> 1
3 -> 2 1 3 -> 4 -> 2
3 -> 4 2 3 -> 4
4 -> 1 3 4 -> 2 -> 1
4 -> 2 -1 4 -> 2
4 -> 3 1 4 -> 2 -> 1 -> 3
</pre>
Line 4,613 ⟶ 5,440:
I have run this program successfully in Chibi, Gauche, and CHICKEN 5 Schemes. (One may need an extension to run R7RS code in CHICKEN.)
<
;;;
;;; See https://en.wikipedia.org/w/index.php?title=Floyd%E2%80%93Warshall_algorithm&oldid=1082310013
Line 4,750 ⟶ 5,577:
(display " ")
(display-path (find-path next-vertex u v))
(newline)))))</
{{out}}
Line 4,771 ⟶ 5,598:
=={{header|SequenceL}}==
{{trans|Go}}
<
import <Utilities/Math.sl>;
Line 4,827 ⟶ 5,654:
vertex(4, [arc(2,-1)])];
in
floydWarshall(graph);</
{{out}}
Line 4,836 ⟶ 5,663:
=={{header|Sidef}}==
{{trans|Ruby}}
<
var dist = n.of {|i| n.of { |j| i == j ? 0 : Inf }}
var nxt = n.of { n.of(nil) }
Line 4,868 ⟶ 5,695:
var n = 4
var edge = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]
print floyd_warshall(n, edge)</
{{out}}
<pre>
Line 4,897 ⟶ 5,724:
<
Floyd-Warshall algorithm.
Line 5,222 ⟶ 6,049:
(* sml-indent-level: 2 *)
(* sml-indent-args: 2 *)
(* end: *)</
{{out}}
Line 5,247 ⟶ 6,074:
The implementation of Floyd-Warshall in tcllib is [https://core.tcl.tk/tcllib/finfo?name=modules/struct/graphops.tcl quite readable]; this example merely initialises a graph from an adjacency list then calls the tcllib code:
<
package require struct::graph
package require struct::graph::op
Line 5,277 ⟶ 6,104:
set paths [dict filter $paths value {[0-9]*}] ;# whose cost is not "Inf"
set paths [lsort -stride 2 -index 1 -real -decreasing $paths] ;# and print the longest first
puts $paths</
{{out}}
Line 5,284 ⟶ 6,111:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Sub PrintResult(dist As Double(,), nxt As Integer(,))
Line 5,346 ⟶ 6,173:
End Sub
End Module</
{{out}}
<pre>pair dist path
Line 5,365 ⟶ 6,192:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<
class FloydWarshall {
Line 5,414 ⟶ 6,241:
var weights = [ [1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1] ]
var nVertices = 4
FloydWarshall.doCalcs(weights, nVertices)</
{{out}}
Line 5,434 ⟶ 6,261:
=={{header|zkl}}==
<
V:=dist[0].len();
next:=V.pump(List,V.pump(List,Void.copy).copy); // VxV matrix of Void
Line 5,455 ⟶ 6,282:
}
fcn printM(m){ m.pump(Console.println,rowFmt) }
fcn rowFmt(row){ ("%5s "*row.len()).fmt(row.xplode()) }</
<
dist:=V.pump(List,V.pump(List,Void.copy).copy); // VxV matrix of Void
foreach i in (V){ dist[i][i] = 0 } // zero vertexes
Line 5,476 ⟶ 6,303:
foreach u,v in (V,V){
if(p:=path(next,u,v)) p.println();
}</
{{out}}
<pre>
|