Floyd-Warshall algorithm: Difference between revisions

{{trans|Python}}

 

V rn = 0 .< n

V dist = rn.map(i -> [1'000'000] * @n)

print(‘#. -> #. #4 #.’.format(i + 1, j + 1, dist[i][j], path.map(p -> String(p + 1)).join(‘ -> ’)))

 

 

{{out}}

=={{header|360 Assembly}}==

{{trans|Rexx}}

FLOYDWAR CSECT

USING FLOYDWAR,R13 base register

XDEC DS CL12

YREGS

{{out}}

<pre>

 

 

-- Floyd-Warshall algorithm.

--

 

end;

 

{{out}}

4 -> 2 -1.00000E+00 4 -> 2

4 -> 3 1.00000E+00 4 -> 2 -> 1 -> 3</pre>

 

=={{header|ATS}}==

 

 

Floyd-Warshall algorithm.

 

end

 

 

{{out}}

 

 

Floyd-Warshall algorithm.

 

end

 

 

{{out}}

=={{header|C}}==

Reads the graph from a file, prints out usage on incorrect invocation.

#include<limits.h>

#include<stdlib.h>

return 0;

}

Input file, first row specifies number of vertices and edges.

<pre>

<pre>

C:\rosettaCode>fwGraph.exe fwGraph.txt

pair dist path

1 -> 2 -1 1->3->4->2

=={{header|C sharp|C#}}==

{{trans|Java}}

 

namespace FloydWarshallAlgorithm {

}

}

 

=={{header|C++}}==

#include <vector>

#include <sstream>

std::cin.get();

return 0;

 

{{out}}

I have wrapped the Common Lisp program in a [https://roswell.github.io/ Roswell] script.

 

 

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

 

 

#|-*- mode:lisp -*-|#

#|

 

;;;-------------------------------------------------------------------

 

{{out}}

4 -> 2 -1.0 4 -> 2

4 -> 3 1.0 4 -> 2 -> 1 -> 3</pre>

 

=={{header|D}}==

{{trans|Java}}

 

void main() {

}

}

 

{{out}}

=={{header|EchoLisp}}==

Transcription of the Floyd-Warshall algorithm, with best path computation.

(lib 'matrix)

 

(array-print dist) ;; show init distances

(floyd-with-path n dist next))

{{out}}

<pre>

 

=={{header|Elixir}}==

def main(n, edge) do

{dist, next} = setup(n, edge)

 

edge = [{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}]

 

{{out}}

=={{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)

|_->yield None}

yield! fN x y |> Seq.choose id; yield y}))

 

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

{{out}}

<pre>

 

 

 

use, intrinsic :: ieee_arithmetic

end do

 

 

{{out}}

=={{header|FreeBASIC}}==

{{trans|Java}}

 

Const POSITIVE_INFINITY As Double = 1.0/0.0

Print

Print "Press any key to quit"

 

{{out}}

 

=={{header|Go}}==

import (

}

}

{{out}}

<pre>

=={{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]]

}

}

{{out}}

<pre>pair dist path

 

Necessary imports

import Data.List (union)

import Data.Map hiding (foldr, union)

import Data.Maybe (fromJust, isJust)

import Data.Semigroup

 

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

 

 

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

 

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.

 

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

return $ Shortest (distance a <> distance b) (path a))

 

 

The <code>floydWarshall</code> produces only first steps of shortest paths. Whole paths are build by following function:

 

where

buildPath (i,j)

| otherwise = do k <- path $ fromJust $ lookup (i,j) d

p <- buildPath (k,j)

 

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)

 

'''Examples''':

 

The sample graph:

,((2,3), 3)

,((1,3), -2)

,((3,4), 2)

the helper function

 

{{Out}}

Graph labeled by chars:

 

,(('A','D'), -1)

,(('S','E'), 2)

 

<pre>λ> showShortestPaths "ASDE" (Sum <$> g2)

 

 

# Floyd-Warshall algorithm.

#

every e := !edges do m := max (m, e[1], e[3])

return m

 

{{out}}

=={{header|J}}==

 

for_j. i.#y do.

y=. y <. j ({"1 +/ {) y

end.

 

Example use:

 

0 _ _2 _ NB. 1->3 costs _2

4 0 3 _ NB. 2->1 costs 4; 2->3 costs 3

4 0 2 4

5 1 0 2

 

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.

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.

end.

i.0 0

 

Draft output:

 

pair dist path

1->2 _1 1->3->4->2

4->1 3 4->2->1

4->2 _1 4->2

 

=={{header|Java}}==

import java.util.Arrays;

 

}

}

<pre>pair dist path

1 -> 2 -1 1 -> 3 -> 4 -> 2

 

=={{header|JavaScript}}==

graph.push([]);

graph[i].push(i == j ? 0 : 9999999);

}

 

}

 

}

}

}

 

 

=={{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:

def weights: {

"1": {"3": -2},

"3": {"4": 2},

"4": {"2": -1}

 

The algorithm given here is a direct implementation of the definitional algorithm:

. as $weights

| keys_unsorted as $nodes

 

 

{{out}}

<pre>{

=={{header|Julia}}==

{{trans|Java}}

# v0.6

 

end

 

 

=={{header|Kotlin}}==

{{trans|Java}}

 

object FloydWarshall {

val nVertices = 4

FloydWarshall.doCalcs(weights, nVertices)

 

{{out}}

=={{header|Lua}}==

{{trans|D}}

print("pair dist path")

for i=0, #nxt do

}

numVertices = 4

{{out}}

<pre>pair dist path

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

4 \[DirectedEdge] 2, 2 \[DirectedEdge] 1, 2 \[DirectedEdge] 3},

EdgeWeight -> {(1 \[DirectedEdge] 3) -> -2, (3 \[DirectedEdge] 4) ->

Catenate[

Table[{vl[[i]], vl[[j]], dm[[i, j]]}, {i, Length[vl]}, {j,

{{out}}

<pre>1 2 -1.

4 3 1.</pre>

 

 

=={{header|Modula-2}}==

FROM FormatString IMPORT FormatString;

FROM SpecialReals IMPORT Infinity;

 

ReadChar

 

=={{header|Nim}}==

{{trans|D}}

 

type

let numVertices = 4

 

 

{{out}}

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.

#

every e := !edges do m := max (m, e[1], e[3])

return m

 

{{out}}

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.

 

done

done

 

{{out}}

 

=={{header|Perl}}==

my $edges = shift;

my (@dist, @seq);

 

my $graph = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]];

{{out}}

<pre>pair dist path

=={{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>

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

 

=={{header|PHP}}==

$graph = array();

for ($i = 0; $i < 10; ++$i) {

 

print_r($graph);

 

=={{header|Prolog}}==

Works with SWI-Prolog as of Jan 2019

 

path(List, To, From, [From], W) :-

find_path(D, From, To, Path, Weight),(

atomic_list_concat(Path, ' -> ', PPath),

{{output}}

<pre>?- print_all_paths.

=={{header|Python}}==

{{trans|Ruby}}

from itertools import product

 

 

if __name__ == '__main__':

 

{{output}}

=={{header|Racket}}==

{{trans|EchoLisp}}

(require math/array)

(mdist dist+ 1 3)

(path next+ 7 6)

 

{{out}}

{{trans|Ruby}}

 

my @dist = [0, |(Inf xx $n-1)], *.Array.rotate(-1) … !*[*-1];

my @next = [0 xx $n] xx $n;

}

 

{{out}}

<pre> Pair Distance Path

 

 

# Floyd-Warshall algorithm.

#

write (* , '(1000A1)') (str(j:j), j = 1, trimr (str))

}

 

{{out}}

 

=={{header|REXX}}==

v= 4 /*███ {1} ███*/ /*number of vertices in weighted graph.*/

@.= 99999999 /*███ 4 / \ -2 ███*/ /*the default distance (edge weight). */

say $ center(f '───►' t, w) right(@.f.t, w % 2)

end /*t*/ /* [↑] the distance between 2 vertices*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ruby}}==

dist = Array.new(n){|i| Array.new(n){|j| i==j ? 0 : Float::INFINITY}}

nxt = Array.new(n){Array.new(n)}

n = 4

edge = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]

 

{{out}}

and it requires no special value for infinity.

 

 

#[derive(Clone, Debug, PartialEq, Eq, Hash)]

print_results(&weights, paths.as_ref(), |index| index + 1);

}

 

{{out}}

4 -> 2: -1 4 -> 2

4 -> 3: 1 4 -> 2 -> 1 -> 3

</pre>

 

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

(display " ")

(display-path (find-path next-vertex u v))

 

{{out}}

=={{header|SequenceL}}==

{{trans|Go}}

import <Utilities/Math.sl>;

 

vertex(4, [arc(2,-1)])];

in

 

{{out}}

=={{header|Sidef}}==

{{trans|Ruby}}

var dist = n.of {|i| n.of { |j| i == j ? 0 : Inf }}

var nxt = n.of { n.of(nil) }

var n = 4

var edge = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]

{{out}}

<pre>

 

 

Floyd-Warshall algorithm.

 

(* sml-indent-level: 2 *)

(* sml-indent-args: 2 *)

 

{{out}}

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

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

 

{{out}}

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Sub PrintResult(dist As Double(,), nxt As Integer(,))

End Sub

 

{{out}}

<pre>pair dist path

{{trans|Kotlin}}

{{libheader|Wren-fmt}}

 

class FloydWarshall {

var weights = [ [1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1] ]

var nVertices = 4

 

{{out}}

 

=={{header|zkl}}==

V:=dist[0].len();

next:=V.pump(List,V.pump(List,Void.copy).copy); // VxV matrix of Void

}

fcn printM(m){ m.pump(Console.println,rowFmt) }

dist:=V.pump(List,V.pump(List,Void.copy).copy); // VxV matrix of Void

foreach i in (V){ dist[i][i] = 0 } // zero vertexes

foreach u,v in (V,V){

if(p:=path(next,u,v)) p.println();

{{out}}

<pre>