Floyd-Warshall algorithm: Difference between revisions

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

{{trans|Java}}

<lang csharp>using System;

namespace FloydWarshallAlgorithm {

class Program {

static void FloydWarshall(int[,] weights, int numVerticies) {

double[,] dist = new double[numVerticies, numVerticies];

for (int i = 0; i < numVerticies; i++) {

for (int j = 0; j < numVerticies; j++) {

dist[i, j] = double.PositiveInfinity;

}

}

for (int i = 0; i < weights.GetLength(0); i++) {

dist[weights[i, 0] - 1, weights[i, 1] - 1] = weights[i, 2];

}

int[,] next = new int[numVerticies, numVerticies];

for (int i = 0; i < numVerticies; i++) {

for (int j = 0; j < numVerticies; j++) {

if (i != j) {

next[i, j] = j + 1;

}

}

}

for (int k = 0; k < numVerticies; k++) {

for (int i = 0; i < numVerticies; i++) {

for (int j = 0; j < numVerticies; j++) {

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

}

static void PrintResult(double[,] dist, int[,] next) {

Console.WriteLine("pair dist path");

for (int i = 0; i < next.GetLength(0); i++) {

for (int j = 0; j < next.GetLength(1); j++) {

if (i != j) {

int u = i + 1;

int v = j + 1;

string path = string.Format("{0} -> {1} {2,2:G} {3}", u, v, dist[i, j], u);

do {

u = next[u - 1, v - 1];

path += " -> " + u;

} while (u != v);

Console.WriteLine(path);

}

}

}

}

static void Main(string[] args) {

int[,] weights = { { 1, 3, -2 }, { 2, 1, 4 }, { 2, 3, 3 }, { 3, 4, 2 }, { 4, 2, -1 } };

int numVerticies = 4;

FloydWarshall(weights, numVerticies);

}

}

}</lang>

</pre>

=={{header|F_Sharp|F#}}==

===Floyd's algorithm===

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

let ix n g=Seq.init (pown g n) (fun x->List.unfold(fun (a,b)->if a=0 then None else Some(b%g,(a-1,b/g)))(n,x))

let fN w (i,j,k)=match Map.tryFind(i,j) w,Map.tryFind(i,k) w,Map.tryFind(k,j) w with

|(None ,Some j,Some k)->Some(j+k)

|(Some i,Some j,Some k)->if (j+k) < i then Some(j+k) else None

|_ ->None

let n,z=ix 3 (Array.length n)|>Seq.choose(fun (i::j::k::_)->if i<>j&&i<>k&&j<>k then Some(n.[i],n.[j],n.[k]) else None)

|>Seq.fold(fun (n,n') ((i,j,k) as g)->match fN n g with |Some g->(Map.add (i,j) g n,Map.add (i,j) k n')|_->(n,n')) (g,Map.empty)

(n,(fun x y->seq{

let rec fN n g=seq{

match Map.tryFind (n,g) z with

|Some r->yield! fN n r; yield Some r;yield! fN r g

|_->yield None}

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

</lang>

===The Task===

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

</lang>

{{out}}

<pre>

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]

=={{header|Raku}}==

(formerly Perl 6)

{{works with|Rakudo|2016.12}}

{{trans|Ruby}}

<lang perl6>sub Floyd-Warshall (Int $n, @edge) {

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

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

for @edge -> ($u, $v, $w) {

@dist[$u-1;$v-1] = $w;

@next[$u-1;$v-1] = $v-1;

}

for [X] ^$n xx 3 -> ($k, $i, $j) {

if @dist[$i;$j] > my $sum = @dist[$i;$k] + @dist[$k;$j] {

@dist[$i;$j] = $sum;

@next[$i;$j] = @next[$i;$k];

}

}

say ' Pair Distance Path';

for [X] ^$n xx 2 -> ($i, $j){

next if $i == $j;

my @path = $i;

@path.push: @next[@path[*-1];$j] until @path[*-1] == $j;

printf("%d → %d %4d %s\n", $i+1, $j+1, @dist[$i;$j],

@path.map( *+1 ).join(' → '));

}

}

Floyd-Warshall(4, [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]);</lang>

{{out}}

<pre> Pair Distance 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>