Rosetta Code

Floyd-Warshall algorithm: Difference between revisions

Page Discussion

Floyd-Warshall algorithm (view source)

Revision as of 13:26, 27 August 2022

1,918 bytes added ,  1 year ago
m
syntax highlighting fixup automation
m (syntax highlighting fixup automation)
Line 31:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">F floyd_warshall(n, edge)
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)])</langsyntaxhighlight>
 
{{out}}
Line 74:
=={{header|360 Assembly}}==
{{trans|Rexx}}
<langsyntaxhighlight lang="360asm">* Floyd-Warshall algorithm - 06/06/2018
FLOYDWAR CSECT
USING FLOYDWAR,R13 base register
Line 149:
XDEC DS CL12
YREGS
END FLOYDWAR</langsyntaxhighlight>
{{out}}
<pre>
Line 170:
 
 
<langsyntaxhighlight lang="ada">--
-- Floyd-Warshall algorithm.
--
Line 352:
 
end;
end floyd_warshall_task;</langsyntaxhighlight>
 
{{out}}
Line 384:
 
 
<langsyntaxhighlight lang="ats">(*
Floyd-Warshall algorithm.
 
Line 676:
end
 
end</langsyntaxhighlight>
 
{{out}}
Line 703:
 
 
<langsyntaxhighlight lang="ats">(*
Floyd-Warshall algorithm.
 
Line 1,245:
end
 
(*------------------------------------------------------------------*)</langsyntaxhighlight>
 
{{out}}
Line 1,266:
=={{header|C}}==
Reads the graph from a file, prints out usage on incorrect invocation.
<syntaxhighlight lang="c">
<lang C>
#include<limits.h>
#include<stdlib.h>
Line 1,342:
return 0;
}
</syntaxhighlight>
</lang>
Input file, first row specifies number of vertices and edges.
<pre>
Line 1,371:
 
VERSION 2. Usando una librería experimental, que pronto será liberada en GitHub, desarrollé la versión anterior del programa. La librería trabaja con memoria dinámica, tanto para strings, como para arrays de un tipo y multitipo. En el ejemplo, se usan funciones para arrays de un tipo. Lo que busco con esta librería experimental, es simplificar la programación, elevar el nivel de abstracción del lenguaje C (un poco), y lograr código elegante.
<syntaxhighlight lang="c">
<lang C>
#include<limits.h>
#include "gadget.h"
Line 1,496:
return graph;
}
</syntaxhighlight>
</lang>
{{out}}
Archivo fuente: floyd_data.txt
Line 1,527:
=={{header|C sharp|C#}}==
{{trans|Java}}
<langsyntaxhighlight lang="csharp">using System;
 
namespace FloydWarshallAlgorithm {
Line 1,591:
}
}
}</langsyntaxhighlight>
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <iostream>
#include <vector>
#include <sstream>
Line 1,667:
std::cin.get();
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 1,695:
 
 
<langsyntaxhighlight lang="lisp">#!/bin/sh
#|-*- mode:lisp -*-|#
#|
Line 1,880:
 
;;;-------------------------------------------------------------------
;;; vim: set ft=lisp lisp:</langsyntaxhighlight>
 
{{out}}
Line 1,901:
=={{header|D}}==
{{trans|Java}}
<langsyntaxhighlight Dlang="d">import std.stdio;
 
void main() {
Line 1,970:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,989:
=={{header|EchoLisp}}==
Transcription of the Floyd-Warshall algorithm, with best path computation.
<langsyntaxhighlight lang="scheme">
(lib 'matrix)
 
Line 2,031:
(array-print dist) ;; show init distances
(floyd-with-path n dist next))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,070:
 
=={{header|Elixir}}==
<langsyntaxhighlight lang="elixir">defmodule Floyd_Warshall do
def main(n, edge) do
{dist, next} = setup(n, edge)
Line 2,113:
 
edge = [{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}]
Floyd_Warshall.main(4, edge)</langsyntaxhighlight>
 
{{out}}
Line 2,134:
=={{header|F_Sharp|F#}}==
===Floyd's algorithm===
<langsyntaxhighlight lang="fsharp">
//Floyd's algorithm: Nigel Galloway August 5th 2018
let Floyd (n:'a[]) (g:Map<('a*'a),int>)= //nodes graph(Map of adjacency list)
Line 2,150:
|_->yield None}
yield! fN x y |> Seq.choose id; yield y}))
</syntaxhighlight>
</lang>
 
===The Task===
<langsyntaxhighlight lang="fsharp">
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>
</lang>
{{out}}
<pre>
Line 2,179:
 
 
<langsyntaxhighlight lang="fortran">module floyd_warshall_algorithm
 
use, intrinsic :: ieee_arithmetic
Line 2,331:
end do
 
end program floyd_warshall_task</langsyntaxhighlight>
 
{{out}}
Line 2,352:
=={{header|FreeBASIC}}==
{{trans|Java}}
<langsyntaxhighlight lang="freebasic">' FB 1.05.0 Win64
 
Const POSITIVE_INFINITY As Double = 1.0/0.0
Line 2,413:
Print
Print "Press any key to quit"
Sleep</langsyntaxhighlight>
 
{{out}}
Line 2,433:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
import (
Line 2,545:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,565:
=={{header|Groovy}}==
{{trans|Java}}
<langsyntaxhighlight lang="groovy">class FloydWarshall {
static void main(String[] args) {
int[][] weights = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]
Line 2,625:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>pair dist path
Line 2,644:
 
Necessary imports
<langsyntaxhighlight lang="haskell">import Control.Monad (join)
import Data.List (union)
import Data.Map hiding (foldr, union)
import Data.Maybe (fromJust, isJust)
import Data.Semigroup
import Prelude hiding (lookup, filter)</langsyntaxhighlight>
 
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...)
 
<langsyntaxhighlight lang="haskell">data Shortest b a = Shortest { distance :: a, path :: [b] }
deriving Show</langsyntaxhighlight>
 
Next we note that shortest paths form a semigroup with following "addition" rule:
 
<langsyntaxhighlight lang="haskell">instance (Ord a, Eq b) => Semigroup (Shortest b a) where
a <> b = case distance a `compare` distance b of
GT -> b
LT -> a
EQ -> a { path = path a `union` path b }</langsyntaxhighlight>
 
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,669:
 
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>:
<langsyntaxhighlight lang="haskell">floydWarshall v dist = foldr innerCycle (Just <$> dist) v
where
innerCycle k dist = (newDist <$> v <*> v) `setTo` dist
Line 2,678:
return $ Shortest (distance a <> distance b) (path a))
 
setTo = unionWith (<>) . fromList</langsyntaxhighlight>
 
The <code>floydWarshall</code> produces only first steps of shortest paths. Whole paths are build by following function:
 
<langsyntaxhighlight lang="haskell">buildPaths d = mapWithKey (\pair s -> s { path = buildPath pair}) d
where
buildPath (i,j)
Line 2,688:
| otherwise = do k <- path $ fromJust $ lookup (i,j) d
p <- buildPath (k,j)
[i : p]</langsyntaxhighlight>
 
All pre- and postprocessing is done by the main function <code>findMinDistances</code>:
<langsyntaxhighlight lang="haskell">findMinDistances v g =
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)</langsyntaxhighlight>
 
'''Examples''':
 
The sample graph:
<langsyntaxhighlight lang="haskell">g = fromList [((2,1), 4)
,((2,3), 3)
,((1,3), -2)
,((3,4), 2)
,((4,2), -1)]</langsyntaxhighlight>
the helper function
<langsyntaxhighlight lang="haskell">showShortestPaths v g = mapM_ print $ toList $ findMinDistances v g</langsyntaxhighlight>
 
{{Out}}
Line 2,757:
Graph labeled by chars:
 
<langsyntaxhighlight lang="haskell">g2 = fromList [(('A','S'), 1)
,(('A','D'), -1)
,(('S','E'), 2)
,(('D','E'), 4)]</langsyntaxhighlight>
 
<pre>λ> showShortestPaths "ASDE" (Sum <$> g2)
Line 2,774:
 
 
<langsyntaxhighlight lang="icon">#
# Floyd-Warshall algorithm.
#
Line 2,890:
every e := !edges do m := max (m, e[1], e[3])
return m
end</langsyntaxhighlight>
 
{{out}}
Line 2,911:
=={{header|J}}==
 
<langsyntaxhighlight Jlang="j">floyd=: verb define
for_j. i.#y do.
y=. y <. j ({"1 +/ {) y
end.
)</langsyntaxhighlight>
 
Example use:
 
<langsyntaxhighlight Jlang="j">graph=: ".;._2]0 :0
0 _ _2 _ NB. 1->3 costs _2
4 0 3 _ NB. 2->1 costs 4; 2->3 costs 3
Line 2,930:
4 0 2 4
5 1 0 2
3 _1 1 0</langsyntaxhighlight>
 
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,940:
This draft task currently asks for path reconstruction, which is a different (related) algorithm:
 
<langsyntaxhighlight Jlang="j">floydrecon=: verb define
n=. ($y)$_(I._=,y)},($$i.@#)y
for_j. i.#y do.
Line 2,972:
end.
i.0 0
)</langsyntaxhighlight>
 
Draft output:
 
<langsyntaxhighlight Jlang="j"> task graph
pair dist path
1->2 _1 1->3->4->2
Line 2,989:
4->1 3 4->2->1
4->2 _1 4->2
4->3 1 4->2->1->3</langsyntaxhighlight>
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">import static java.lang.String.format;
import java.util.Arrays;
 
Line 3,049:
}
}
}</langsyntaxhighlight>
<pre>pair dist path
1 -> 2 -1 1 -> 3 -> 4 -> 2
Line 3,066:
=={{header|JavaScript}}==
{{output?|Javascript}}
<langsyntaxhighlight lang="javascript">var graph = [];
for (i = 0; i < 10; ++i) {
graph.push([]);
Line 3,086:
}
 
console.log(graph);</langsyntaxhighlight>
 
=={{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">
<lang jq>
def weights: {
"1": {"3": -2},
Line 3,097:
"3": {"4": 2},
"4": {"2": -1}
};</langsyntaxhighlight>
 
The algorithm given here is a direct implementation of the definitional algorithm:
<langsyntaxhighlight lang="jq">def fwi:
. as $weights
| keys_unsorted as $nodes
Line 3,120:
 
 
weights | fwi</langsyntaxhighlight>
{{out}}
<pre>{
Line 3,151:
=={{header|Julia}}==
{{trans|Java}}
<langsyntaxhighlight lang="julia"># Floyd-Warshall algorithm: https://rosettacode.org/wiki/Floyd-Warshall_algorithm
# v0.6
 
Line 3,188:
end
 
floydwarshall([1 3 -2; 2 1 4; 2 3 3; 3 4 2; 4 2 -1], 4)</langsyntaxhighlight>
 
=={{header|Kotlin}}==
{{trans|Java}}
<langsyntaxhighlight lang="scala">// version 1.1
 
object FloydWarshall {
Line 3,249:
val nVertices = 4
FloydWarshall.doCalcs(weights, nVertices)
}</langsyntaxhighlight>
 
{{out}}
Line 3,270:
=={{header|Lua}}==
{{trans|D}}
<langsyntaxhighlight lang="lua">function printResult(dist, nxt)
print("pair dist path")
for i=0, #nxt do
Line 3,334:
}
numVertices = 4
floydWarshall(weights, numVertices)</langsyntaxhighlight>
{{out}}
<pre>pair dist path
Line 3,352:
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">g = Graph[{1 \[DirectedEdge] 3, 3 \[DirectedEdge] 4,
4 \[DirectedEdge] 2, 2 \[DirectedEdge] 1, 2 \[DirectedEdge] 3},
EdgeWeight -> {(1 \[DirectedEdge] 3) -> -2, (3 \[DirectedEdge] 4) ->
Line 3,363:
Catenate[
Table[{vl[[i]], vl[[j]], dm[[i, j]]}, {i, Length[vl]}, {j,
Length[vl]}]], {x_, x_, _}]]]</langsyntaxhighlight>
{{out}}
<pre>1 2 -1.
Line 3,384:
 
 
<langsyntaxhighlight lang="mercury">:- module floyd_warshall_task.
 
:- interface.
Line 3,589:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</langsyntaxhighlight>
 
{{out}}
Line 3,609:
 
=={{header|Modula-2}}==
<langsyntaxhighlight lang="modula2">MODULE FloydWarshall;
FROM FormatString IMPORT FormatString;
FROM SpecialReals IMPORT Infinity;
Line 3,693:
 
ReadChar
END FloydWarshall.</langsyntaxhighlight>
 
=={{header|Nim}}==
{{trans|D}}
<langsyntaxhighlight Nimlang="nim">import sequtils, strformat
 
type
Line 3,751:
let numVertices = 4
 
floydWarshall(weights, numVertices)</langsyntaxhighlight>
 
{{out}}
Line 3,776:
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.
 
<langsyntaxhighlight lang="objecticon">#
# Floyd-Warshall algorithm.
#
Line 3,892:
every e := !edges do m := max (m, e[1], e[3])
return m
end</langsyntaxhighlight>
 
{{out}}
Line 3,917:
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.
 
<langsyntaxhighlight lang="ocaml">(*
Floyd-Warshall algorithm.
 
Line 4,126:
done
done
;;</langsyntaxhighlight>
 
{{out}}
Line 4,146:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">sub FloydWarshall{
my $edges = shift;
my (@dist, @seq);
Line 4,195:
 
my $graph = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]];
FloydWarshall($graph);</langsyntaxhighlight>
{{out}}
<pre>pair dist path
Line 4,213:
=={{header|Phix}}==
Direct translation of the wikipedia pseudocode
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<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 4,261:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 4,280:
 
=={{header|PHP}}==
<langsyntaxhighlight lang="php"><?php
$graph = array();
for ($i = 0; $i < 10; ++$i) {
Line 4,302:
 
print_r($graph);
?></langsyntaxhighlight>
 
=={{header|Prolog}}==
Works with SWI-Prolog as of Jan 2019
<langsyntaxhighlight lang="prolog">:- use_module(library(clpfd)).
 
path(List, To, From, [From], W) :-
Line 4,332:
find_path(D, From, To, Path, Weight),(
atomic_list_concat(Path, ' -> ', PPath),
format('~p -> ~p\t ~p\t~w~n', [From, To, Weight, PPath]))).</langsyntaxhighlight>
{{output}}
<pre>?- print_all_paths.
Line 4,354:
=={{header|Python}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="python">from math import inf
from itertools import product
 
Line 4,382:
 
if __name__ == '__main__':
floyd_warshall(4, [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]])</langsyntaxhighlight>
 
{{output}}
Line 4,401:
=={{header|Racket}}==
{{trans|EchoLisp}}
<langsyntaxhighlight lang="racket">#lang typed/racket
(require math/array)
Line 4,476:
(mdist dist+ 1 3)
(path next+ 7 6)
(path next+ 6 7))</langsyntaxhighlight>
 
{{out}}
Line 4,521:
{{trans|Ruby}}
 
<syntaxhighlight lang="raku" perl6line>sub Floyd-Warshall (Int $n, @edge) {
my @dist = [0, |(Inf xx $n-1)], *.Array.rotate(-1) … !*[*-1];
my @next = [0 xx $n] xx $n;
Line 4,547:
}
 
Floyd-Warshall(4, [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]);</langsyntaxhighlight>
{{out}}
<pre> Pair Distance Path
Line 4,571:
 
 
<langsyntaxhighlight lang="ratfor">#
# Floyd-Warshall algorithm.
#
Line 4,824:
write (* , '(1000A1)') (str(j:j), j = 1, trimr (str))
}
end</langsyntaxhighlight>
 
{{out}}
Line 4,871:
 
=={{header|REXX}}==
<langsyntaxhighlight lang="rexx">/*REXX program uses Floyd─Warshall algorithm to find shortest distance between vertices.*/
v= 4 /*███ {1} ███*/ /*number of vertices in weighted graph.*/
@.= 99999999 /*███ 4 / \ -2 ███*/ /*the default distance (edge weight). */
Line 4,896:
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. */</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 4,917:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">def floyd_warshall(n, edge)
dist = Array.new(n){|i| Array.new(n){|j| i==j ? 0 : Float::INFINITY}}
nxt = Array.new(n){Array.new(n)}
Line 4,951:
n = 4
edge = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]
floyd_warshall(n, edge)</langsyntaxhighlight>
 
{{out}}
Line 4,976:
and it requires no special value for infinity.
 
<langsyntaxhighlight lang="rust">pub type Edge = (usize, usize);
 
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
Line 5,189:
print_results(&weights, paths.as_ref(), |index| index + 1);
}
</syntaxhighlight>
</lang>
 
{{out}}
Line 5,212:
I have run this program successfully in Chibi, Gauche, and CHICKEN 5 Schemes. (One may need an extension to run R7RS code in CHICKEN.)
 
<langsyntaxhighlight lang="scheme">;;; Floyd-Warshall algorithm.
;;;
;;; See https://en.wikipedia.org/w/index.php?title=Floyd%E2%80%93Warshall_algorithm&oldid=1082310013
Line 5,349:
(display " ")
(display-path (find-path next-vertex u v))
(newline)))))</langsyntaxhighlight>
 
{{out}}
Line 5,370:
=={{header|SequenceL}}==
{{trans|Go}}
<langsyntaxhighlight lang="sequencel">import <Utilities/Sequence.sl>;
import <Utilities/Math.sl>;
 
Line 5,426:
vertex(4, [arc(2,-1)])];
in
floydWarshall(graph);</langsyntaxhighlight>
 
{{out}}
Line 5,435:
=={{header|Sidef}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="ruby">func floyd_warshall(n, edge) {
var dist = n.of {|i| n.of { |j| i == j ? 0 : Inf }}
var nxt = n.of { n.of(nil) }
Line 5,467:
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)</langsyntaxhighlight>
{{out}}
<pre>
Line 5,496:
 
 
<langsyntaxhighlight lang="sml">(*
Floyd-Warshall algorithm.
 
Line 5,821:
(* sml-indent-level: 2 *)
(* sml-indent-args: 2 *)
(* end: *)</langsyntaxhighlight>
 
{{out}}
Line 5,846:
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:
 
<langsyntaxhighlight Tcllang="tcl">package require Tcl 8.5 ;# for {*} and [dict]
package require struct::graph
package require struct::graph::op
Line 5,876:
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</langsyntaxhighlight>
 
{{out}}
Line 5,883:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Module Module1
 
Sub PrintResult(dist As Double(,), nxt As Integer(,))
Line 5,945:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>pair dist path
Line 5,964:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight lang="ecmascript">import "/fmt" for Fmt
 
class FloydWarshall {
Line 6,013:
var weights = [ [1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1] ]
var nVertices = 4
FloydWarshall.doCalcs(weights, nVertices)</langsyntaxhighlight>
 
{{out}}
Line 6,033:
 
=={{header|zkl}}==
<langsyntaxhighlight lang="zkl">fcn FloydWarshallWithPathReconstruction(dist){ // dist is munged
V:=dist[0].len();
next:=V.pump(List,V.pump(List,Void.copy).copy); // VxV matrix of Void
Line 6,054:
}
fcn printM(m){ m.pump(Console.println,rowFmt) }
fcn rowFmt(row){ ("%5s "*row.len()).fmt(row.xplode()) }</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">const V=4;
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 6,075:
foreach u,v in (V,V){
if(p:=path(next,u,v)) p.println();
}</langsyntaxhighlight>
{{out}}
<pre>
Thundergnat
10,327

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/327593"