Floyd-Warshall algorithm: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|C}}) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
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 384:
<
Floyd-Warshall algorithm.
Line 676:
end
end</
{{out}}
Line 703:
<
Floyd-Warshall algorithm.
Line 1,245:
end
(*------------------------------------------------------------------*)</
{{out}}
Line 1,266:
=={{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:
return 0;
}
</syntaxhighlight>
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">
#include<limits.h>
#include "gadget.h"
Line 1,496:
return graph;
}
</syntaxhighlight>
{{out}}
Archivo fuente: floyd_data.txt
Line 1,527:
=={{header|C sharp|C#}}==
{{trans|Java}}
<
namespace FloydWarshallAlgorithm {
Line 1,591:
}
}
}</
=={{header|C++}}==
<
#include <vector>
#include <sstream>
Line 1,667:
std::cin.get();
return 0;
}</
{{out}}
Line 1,695:
<
#|-*- mode:lisp -*-|#
#|
Line 1,880:
;;;-------------------------------------------------------------------
;;; vim: set ft=lisp lisp:</
{{out}}
Line 1,901:
=={{header|D}}==
{{trans|Java}}
<
void main() {
Line 1,970:
}
}
}</
{{out}}
Line 1,989:
=={{header|EchoLisp}}==
Transcription of the Floyd-Warshall algorithm, with best path computation.
<
(lib 'matrix)
Line 2,031:
(array-print dist) ;; show init distances
(floyd-with-path n dist next))
</syntaxhighlight>
{{out}}
<pre>
Line 2,070:
=={{header|Elixir}}==
<
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)</
{{out}}
Line 2,134:
=={{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 2,150:
|_->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 2,179:
<
use, intrinsic :: ieee_arithmetic
Line 2,331:
end do
end program floyd_warshall_task</
{{out}}
Line 2,352:
=={{header|FreeBASIC}}==
{{trans|Java}}
<
Const POSITIVE_INFINITY As Double = 1.0/0.0
Line 2,413:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 2,433:
=={{header|Go}}==
<
import (
Line 2,545:
}
}
}</
{{out}}
<pre>
Line 2,565:
=={{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,625:
}
}
}</
{{out}}
<pre>pair dist path
Line 2,644:
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,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>:
<
where
innerCycle k dist = (newDist <$> v <*> v) `setTo` dist
Line 2,678:
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,688:
| 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,757:
Graph labeled by chars:
<
,(('A','D'), -1)
,(('S','E'), 2)
,(('D','E'), 4)]</
<pre>λ> showShortestPaths "ASDE" (Sum <$> g2)
Line 2,774:
<
# Floyd-Warshall algorithm.
#
Line 2,890:
every e := !edges do m := max (m, e[1], e[3])
return m
end</
{{out}}
Line 2,911:
=={{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
Line 2,930:
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,940:
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,972:
end.
i.0 0
)</
Draft output:
<
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</
=={{header|Java}}==
<
import java.util.Arrays;
Line 3,049:
}
}
}</
<pre>pair dist path
1 -> 2 -1 1 -> 3 -> 4 -> 2
Line 3,066:
=={{header|JavaScript}}==
{{output?|Javascript}}
<
for (i = 0; i < 10; ++i) {
graph.push([]);
Line 3,086:
}
console.log(graph);</
=={{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 3,097:
"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 3,120:
weights | fwi</
{{out}}
<pre>{
Line 3,151:
=={{header|Julia}}==
{{trans|Java}}
<
# v0.6
Line 3,188:
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 3,249:
val nVertices = 4
FloydWarshall.doCalcs(weights, nVertices)
}</
{{out}}
Line 3,270:
=={{header|Lua}}==
{{trans|D}}
<
print("pair dist path")
for i=0, #nxt do
Line 3,334:
}
numVertices = 4
floydWarshall(weights, numVertices)</
{{out}}
<pre>pair dist path
Line 3,352:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
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_, _}]]]</
{{out}}
<pre>1 2 -1.
Line 3,384:
<
:- interface.
Line 3,589:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</
{{out}}
Line 3,609:
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM SpecialReals IMPORT Infinity;
Line 3,693:
ReadChar
END FloydWarshall.</
=={{header|Nim}}==
{{trans|D}}
<
type
Line 3,751:
let numVertices = 4
floydWarshall(weights, numVertices)</
{{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.
<
# Floyd-Warshall algorithm.
#
Line 3,892:
every e := !edges do m := max (m, e[1], e[3])
return m
end</
{{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.
<
Floyd-Warshall algorithm.
Line 4,126:
done
done
;;</
{{out}}
Line 4,146:
=={{header|Perl}}==
<
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);</
{{out}}
<pre>pair dist path
Line 4,213:
=={{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 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>
<!--</
{{out}}
<pre>
Line 4,280:
=={{header|PHP}}==
<
$graph = array();
for ($i = 0; $i < 10; ++$i) {
Line 4,302:
print_r($graph);
?></
=={{header|Prolog}}==
Works with SWI-Prolog as of Jan 2019
<
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]))).</
{{output}}
<pre>?- print_all_paths.
Line 4,354:
=={{header|Python}}==
{{trans|Ruby}}
<
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]])</
{{output}}
Line 4,401:
=={{header|Racket}}==
{{trans|EchoLisp}}
<
(require math/array)
Line 4,476:
(mdist dist+ 1 3)
(path next+ 7 6)
(path next+ 6 7))</
{{out}}
Line 4,521:
{{trans|Ruby}}
<syntaxhighlight lang="raku"
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]]);</
{{out}}
<pre> Pair Distance Path
Line 4,571:
<
# Floyd-Warshall algorithm.
#
Line 4,824:
write (* , '(1000A1)') (str(j:j), j = 1, trimr (str))
}
end</
{{out}}
Line 4,871:
=={{header|REXX}}==
<
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. */</
{{out|output|text= when using the default inputs:}}
<pre>
Line 4,917:
=={{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,951:
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,976:
and it requires no special value for infinity.
<
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
Line 5,189:
print_results(&weights, paths.as_ref(), |index| index + 1);
}
</syntaxhighlight>
{{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.)
<
;;;
;;; 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)))))</
{{out}}
Line 5,370:
=={{header|SequenceL}}==
{{trans|Go}}
<
import <Utilities/Math.sl>;
Line 5,426:
vertex(4, [arc(2,-1)])];
in
floydWarshall(graph);</
{{out}}
Line 5,435:
=={{header|Sidef}}==
{{trans|Ruby}}
<
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)</
{{out}}
<pre>
Line 5,496:
<
Floyd-Warshall algorithm.
Line 5,821:
(* sml-indent-level: 2 *)
(* sml-indent-args: 2 *)
(* end: *)</
{{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:
<
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</
{{out}}
Line 5,883:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Sub PrintResult(dist As Double(,), nxt As Integer(,))
Line 5,945:
End Sub
End Module</
{{out}}
<pre>pair dist path
Line 5,964:
{{trans|Kotlin}}
{{libheader|Wren-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)</
{{out}}
Line 6,033:
=={{header|zkl}}==
<
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()) }</
<
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();
}</
{{out}}
<pre>
|