Floyd-Warshall algorithm: Difference between revisions

Content added Content deleted
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
(Add source for Rust)
Line 174: Line 174:


typedef struct{
typedef struct{
int sourceVertex, destVertex;
int sourceVertex, destVertex;
int edgeWeight;
int edgeWeight;
}edge;
}edge;


typedef struct{
typedef struct{
int vertices, edges;
int vertices, edges;
edge* edgeMatrix;
edge* edgeMatrix;
}graph;
}graph;


graph loadGraph(char* fileName){
graph loadGraph(char* fileName){
FILE* fp = fopen(fileName,"r");
FILE* fp = fopen(fileName,"r");
graph G;
graph G;
int i;
int i;
fscanf(fp,"%d%d",&G.vertices,&G.edges);
fscanf(fp,"%d%d",&G.vertices,&G.edges);
G.edgeMatrix = (edge*)malloc(G.edges*sizeof(edge));
G.edgeMatrix = (edge*)malloc(G.edges*sizeof(edge));
for(i=0;i<G.edges;i++)
for(i=0;i<G.edges;i++)
fscanf(fp,"%d%d%d",&G.edgeMatrix[i].sourceVertex,&G.edgeMatrix[i].destVertex,&G.edgeMatrix[i].edgeWeight);
fscanf(fp,"%d%d%d",&G.edgeMatrix[i].sourceVertex,&G.edgeMatrix[i].destVertex,&G.edgeMatrix[i].edgeWeight);
fclose(fp);
fclose(fp);
return G;
return G;
}
}


void floydWarshall(graph g){
void floydWarshall(graph g){
int processWeights[g.vertices][g.vertices], processedVertices[g.vertices][g.vertices];
int processWeights[g.vertices][g.vertices], processedVertices[g.vertices][g.vertices];
int i,j,k;
int i,j,k;
for(i=0;i<g.vertices;i++)
for(i=0;i<g.vertices;i++)
for(j=0;j<g.vertices;j++){
for(j=0;j<g.vertices;j++){
processWeights[i][j] = SHRT_MAX;
processWeights[i][j] = SHRT_MAX;
processedVertices[i][j] = (i!=j)?j+1:0;
processedVertices[i][j] = (i!=j)?j+1:0;
}
}
for(i=0;i<g.edges;i++)
for(i=0;i<g.edges;i++)
processWeights[g.edgeMatrix[i].sourceVertex-1][g.edgeMatrix[i].destVertex-1] = g.edgeMatrix[i].edgeWeight;
processWeights[g.edgeMatrix[i].sourceVertex-1][g.edgeMatrix[i].destVertex-1] = g.edgeMatrix[i].edgeWeight;
for(i=0;i<g.vertices;i++)
for(i=0;i<g.vertices;i++)
for(j=0;j<g.vertices;j++)
for(j=0;j<g.vertices;j++)
for(k=0;k<g.vertices;k++){
for(k=0;k<g.vertices;k++){
if(processWeights[j][i] + processWeights[i][k] < processWeights[j][k]){
if(processWeights[j][i] + processWeights[i][k] < processWeights[j][k]){
processWeights[j][k] = processWeights[j][i] + processWeights[i][k];
processWeights[j][k] = processWeights[j][i] + processWeights[i][k];
processedVertices[j][k] = processedVertices[j][i];
processedVertices[j][k] = processedVertices[j][i];
}
}
}
}
printf("pair dist path");
printf("pair dist path");
for(i=0;i<g.vertices;i++)
for(i=0;i<g.vertices;i++)
for(j=0;j<g.vertices;j++){
for(j=0;j<g.vertices;j++){
if(i!=j){
if(i!=j){
printf("\n%d -> %d %3d %5d",i+1,j+1,processWeights[i][j],i+1);
printf("\n%d -> %d %3d %5d",i+1,j+1,processWeights[i][j],i+1);
k = i+1;
k = i+1;
do{
do{
k = processedVertices[k-1][j];
k = processedVertices[k-1][j];
printf("->%d",k);
printf("->%d",k);
}while(k!=j+1);
}while(k!=j+1);
}
}
}
}
}
}


int main(int argC,char* argV[]){
int main(int argC,char* argV[]){
if(argC!=2)
if(argC!=2)
printf("Usage : %s <file containing graph data>");
printf("Usage : %s <file containing graph data>");
else
else
floydWarshall(loadGraph(argV[1]));
floydWarshall(loadGraph(argV[1]));
return 0;
return 0;
}
}
</lang>
</lang>
Line 529: Line 529:


(define (floyd-with-path n dist next (d 0))
(define (floyd-with-path n dist next (d 0))
(for* ((k n) (i n) (j n))
(for* ((k n) (i n) (j n))
#:break (< (array-ref dist j j) 0) => 'negative-cycle
#:break (< (array-ref dist j j) 0) => 'negative-cycle
(set! d (+ (array-ref dist i k) (array-ref dist k j)))
(set! d (+ (array-ref dist i k) (array-ref dist k j)))
(when (< d (array-ref dist i j))
(when (< d (array-ref dist i j))
(array-set! dist i j d)
(array-set! dist i j d)
(array-set! next i j (array-ref next i k)))))
(array-set! next i j (array-ref next i k)))))


;; utilities
;; utilities
Line 541: Line 541:
(define (init-edges n dist next)
(define (init-edges n dist next)
(for* ((i n) (j n))
(for* ((i n) (j n))
(array-set! dist i i 0)
(array-set! dist i i 0)
(array-set! next i j null)
(array-set! next i j null)
#:continue (= j i)
#:continue (= j i)
(array-set! dist i j Infinity)
(array-set! dist i j Infinity)
#:continue (< (random) 0.3)
#:continue (< (random) 0.3)
(array-set! dist i j (1+ (random 100)))
(array-set! dist i j (1+ (random 100)))
(array-set! next i j j)))
(array-set! next i j j)))


;; show path from u to v
;; show path from u to v
(define (path u v)
(define (path u v)
(cond
(cond
((= u v) (list u))
((= u v) (list u))
((null? (array-ref next u v)) null)
((null? (array-ref next u v)) null)
(else (cons u (path (array-ref next u v) v)))))
(else (cons u (path (array-ref next u v) v)))))


(define( mdist u v) ;; show computed distance
(define( mdist u v) ;; show computed distance
(array-ref dist u v))
(array-ref dist u v))
(define (task)
(define (task)
(init-edges n dist next)
(init-edges n dist next)
(array-print dist) ;; show init distances
(array-print dist) ;; show init distances
(floyd-with-path n dist next))
(floyd-with-path n dist next))
</lang>
</lang>
{{out}}
{{out}}
Line 904: Line 904:
{{out}}
{{out}}
<pre>
<pre>
pair dist path
pair dist path
1 -> 2 -1 1 -> 3 -> 4 -> 2
1 -> 2 -1 1 -> 3 -> 4 -> 2
1 -> 3 -2 1 -> 3
1 -> 3 -2 1 -> 3
1 -> 4 0 1 -> 3 -> 4
1 -> 4 0 1 -> 3 -> 4
2 -> 1 4 2 -> 1
2 -> 1 4 2 -> 1
2 -> 3 2 2 -> 1 -> 3
2 -> 3 2 2 -> 1 -> 3
2 -> 4 4 2 -> 1 -> 3 -> 4
2 -> 4 4 2 -> 1 -> 3 -> 4
3 -> 1 5 3 -> 4 -> 2 -> 1
3 -> 1 5 3 -> 4 -> 2 -> 1
3 -> 2 1 3 -> 4 -> 2
3 -> 2 1 3 -> 4 -> 2
3 -> 4 2 3 -> 4
3 -> 4 2 3 -> 4
4 -> 1 3 4 -> 2 -> 1
4 -> 1 3 4 -> 2 -> 1
4 -> 2 -1 4 -> 2
4 -> 2 -1 4 -> 2
4 -> 3 1 4 -> 2 -> 1 -> 3
4 -> 3 1 4 -> 2 -> 1 -> 3
</pre>
</pre>


Line 1,252: Line 1,252:
reduce $nodes[] as $u (.;
reduce $nodes[] as $u (.;
reduce $nodes[] as $v (.;
reduce $nodes[] as $v (.;
(.[$u][$w] + .[$w][$v]) as $x
(.[$u][$w] + .[$w][$v]) as $x
| if .[$u][$v] > $x then .[$u][$v] = $x
| if .[$u][$v] > $x then .[$u][$v] = $x
else . end )))
else . end )))
;
;


Line 1,577: Line 1,577:
=={{header|Perl}}==
=={{header|Perl}}==
<lang perl6>sub FloydWarshall{
<lang perl6>sub FloydWarshall{
my $edges = shift;
my $edges = shift;
my (@dist, @seq);
my (@dist, @seq);
my $num_vert = 0;
my $num_vert = 0;
# insert given dists into dist matrix
# insert given dists into dist matrix
map {
map {
$dist[$_->[0] - 1][$_->[1] - 1] = $_->[2];
$dist[$_->[0] - 1][$_->[1] - 1] = $_->[2];
$num_vert = $_->[0] if $num_vert < $_->[0];
$num_vert = $_->[0] if $num_vert < $_->[0];
$num_vert = $_->[1] if $num_vert < $_->[1];
$num_vert = $_->[1] if $num_vert < $_->[1];
} @$edges;
} @$edges;
my @vertices = 0..($num_vert - 1);
my @vertices = 0..($num_vert - 1);
# init sequence/"next" table
# init sequence/"next" table
for my $i(@vertices){
for my $i(@vertices){
for my $j(@vertices){
for my $j(@vertices){
$seq[$i][$j] = $j if $i != $j;
$seq[$i][$j] = $j if $i != $j;
}
}
}
}
# diagonal of dists matrix
# diagonal of dists matrix
#map {$dist[$_][$_] = 0} @vertices;
#map {$dist[$_][$_] = 0} @vertices;
for my $k(@vertices){
for my $k(@vertices){
for my $i(@vertices){
for my $i(@vertices){
next unless defined $dist[$i][$k];
next unless defined $dist[$i][$k];
for my $j(@vertices){
for my $j(@vertices){
next unless defined $dist[$k][$j];
next unless defined $dist[$k][$j];
if($i != $j && (!defined($dist[$i][$j])
if($i != $j && (!defined($dist[$i][$j])
|| $dist[$i][$j] > $dist[$i][$k] + $dist[$k][$j])){
|| $dist[$i][$j] > $dist[$i][$k] + $dist[$k][$j])){
$dist[$i][$j] = $dist[$i][$k] + $dist[$k][$j];
$dist[$i][$j] = $dist[$i][$k] + $dist[$k][$j];
$seq[$i][$j] = $seq[$i][$k];
$seq[$i][$j] = $seq[$i][$k];
}
}
}
}
}
}
}
}
# print table
# print table
print "pair dist path\n";
print "pair dist path\n";
for my $i(@vertices){
for my $i(@vertices){
for my $j(@vertices){
for my $j(@vertices){
next if $i == $j;
next if $i == $j;
my @path = ($i + 1);
my @path = ($i + 1);
while($seq[$path[-1] - 1][$j] != $j){
while($seq[$path[-1] - 1][$j] != $j){
push @path, $seq[$path[-1] - 1][$j] + 1;
push @path, $seq[$path[-1] - 1][$j] + 1;
}
}
push @path, $j + 1;
push @path, $j + 1;
printf "%d -> %d %4d %s\n",
printf "%d -> %d %4d %s\n",
$path[0], $path[-1], $dist[$i][$j], join(' -> ', @path);
$path[0], $path[-1], $dist[$i][$j], join(' -> ', @path);
}
}
}
}
}
}


Line 2,089: Line 2,089:
4 -> 2 -1 4 -> 2
4 -> 2 -1 4 -> 2
4 -> 3 1 4 -> 2 -> 1 -> 3
4 -> 3 1 4 -> 2 -> 1 -> 3
</pre>

=={{header|Rust}}==
The lack of built-in support for multi-dimensional arrays makes the task in Rust
a bit lengthy (without additional crates). The used graph representation leverages
Rust's generics, so that it works with any type that defines addition and ordering
and it requires no special value for infinity.

<lang rust>pub type Edge = (usize, usize);

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Graph<T> {
size: usize,
edges: Vec<Option<T>>,
}

impl<T> Graph<T> {
pub fn new(size: usize) -> Self {
Self {
size,
edges: std::iter::repeat_with(|| None).take(size * size).collect(),
}
}

pub fn new_with(size: usize, f: impl FnMut(Edge) -> Option<T>) -> Self {
let edges = (0..size)
.flat_map(|i| (0..size).map(move |j| (i, j)))
.map(f)
.collect();

Self { size, edges }
}

pub fn with_diagonal(mut self, mut f: impl FnMut(usize) -> Option<T>) -> Self {
self.edges
.iter_mut()
.step_by(self.size + 1)
.enumerate()
.for_each(move |(vertex, edge)| *edge = f(vertex));

self
}

pub fn size(&self) -> usize {
self.size
}

pub fn edge(&self, edge: Edge) -> &Option<T> {
let index = self.edge_index(edge);
&self.edges[index]
}

pub fn edge_mut(&mut self, edge: Edge) -> &mut Option<T> {
let index = self.edge_index(edge);
&mut self.edges[index]
}

fn edge_index(&self, (row, col): Edge) -> usize {
assert!(row < self.size && col < self.size);
row * self.size() + col
}
}

impl<T> std::ops::Index<Edge> for Graph<T> {
type Output = Option<T>;

fn index(&self, index: Edge) -> &Self::Output {
self.edge(index)
}
}

impl<T> std::ops::IndexMut<Edge> for Graph<T> {
fn index_mut(&mut self, index: Edge) -> &mut Self::Output {
self.edge_mut(index)
}
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Paths(Graph<usize>);

impl Paths {
pub fn new<T>(graph: &Graph<T>) -> Self {
Self(Graph::new_with(graph.size(), |(i, j)| {
graph[(i, j)].as_ref().map(|_| j)
}))
}

pub fn vertices(&self, from: usize, to: usize) -> Path<'_> {
assert!(from < self.0.size() && to < self.0.size());

Path {
graph: &self.0,
from: Some(from),
to,
}
}

fn update(&mut self, from: usize, to: usize, via: usize) {
self.0[(from, to)] = self.0[(from, via)];
}
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Path<'a> {
graph: &'a Graph<usize>,
from: Option<usize>,
to: usize,
}

impl<'a> Iterator for Path<'a> {
type Item = usize;

fn next(&mut self) -> Option<Self::Item> {
self.from.map(|from| {
let result = from;

self.from = if result != self.to {
self.graph[(result, self.to)]
} else {
None
};

result
})
}
}

pub fn floyd_warshall<W>(mut result: Graph<W>) -> (Graph<W>, Option<Paths>)
where
W: Copy + std::ops::Add<W, Output = W> + std::cmp::Ord + Default,
{
let mut without_negative_cycles = true;
let mut paths = Paths::new(&result);
let n = result.size();

for k in 0..n {
for i in 0..n {
for j in 0..n {
// Negative cycle detection with T::default as the negative boundary
if i == j && result[(i, j)].filter(|&it| it < W::default()).is_some() {
without_negative_cycles = false;
continue;
}

if let (Some(ik_weight), Some(kj_weight)) = (result[(i, k)], result[(k, j)]) {
let ij_edge = result.edge_mut((i, j));
let ij_weight = ik_weight + kj_weight;

if ij_edge.is_none() {
*ij_edge = Some(ij_weight);
paths.update(i, j, k);
} else {
ij_edge
.as_mut()
.filter(|it| ij_weight < **it)
.map_or((), |it| {
*it = ij_weight;
paths.update(i, j, k);
});
}
}
}
}
}

(result, Some(paths).filter(|_| without_negative_cycles)) // No paths for negative cycles
}

fn format_path<T: ToString>(path: impl Iterator<Item = T>) -> String {
path.fold(String::new(), |mut acc, x| {
if !acc.is_empty() {
acc.push_str(" -> ");
}

acc.push_str(&x.to_string());
acc
})
}

fn print_results<W, V>(weights: &Graph<W>, paths: Option<&Paths>, vertex: impl Fn(usize) -> V)
where
W: std::fmt::Display + Default + Eq,
V: std::fmt::Display,
{
let n = weights.size();

for from in 0..n {
for to in 0..n {
if let Some(weight) = &weights[(from, to)] {
// Skip trivial information (i.e., default weight on the diagonal)
if from == to && *weight == W::default() {
continue;
}

println!(
"{} -> {}: {} \t{}",
vertex(from),
vertex(to),
weight,
format_path(paths.iter().flat_map(|p| p.vertices(from, to)).map(&vertex))
);
}
}
}
}

fn main() {
let graph = {
let mut g = Graph::new(4).with_diagonal(|_| Some(0));
g[(0, 2)] = Some(-2);
g[(1, 0)] = Some(4);
g[(1, 2)] = Some(3);
g[(2, 3)] = Some(2);
g[(3, 1)] = Some(-1);
g
};

let (weights, paths) = floyd_warshall(graph);
// Fixup the vertex name (as we use zero-based indices)
print_results(&weights, paths.as_ref(), |index| index + 1);
}
</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
</pre>
</pre>


Line 2,159: Line 2,396:
{{trans|Ruby}}
{{trans|Ruby}}
<lang ruby>func floyd_warshall(n, edge) {
<lang ruby>func floyd_warshall(n, edge) {
var dist = n.of {|i| n.of { |j| i == j ? 0 : Inf }}
var dist = n.of {|i| n.of { |j| i == j ? 0 : Inf }}
var nxt = n.of { n.of(nil) }
var nxt = n.of { n.of(nil) }
for u,v,w in edge {
for u,v,w in edge {
Line 2,172: Line 2,409:
}
}
}
}
 
var summary = "pair dist path\n"
var summary = "pair dist path\n"
for i,j (^n ~X ^n) {
for i,j (^n ~X ^n) {
Line 2,178: Line 2,415:
var u = i
var u = i
var path = [u]
var path = [u]
while (u != j) {
while (u != j) {
path << (u = nxt[u][j])
path << (u = nxt[u][j])
}
}
path.map!{|u| u+1 }.join!(" -> ")
path.map!{|u| u+1 }.join!(" -> ")
summary += ("%d -> %d  %4d  %s\n" % (i+1, j+1, dist[i][j], path))
summary += ("%d -> %d %4d %s\n" % (i+1, j+1, dist[i][j], path))
}
}


Line 2,337: Line 2,574:
a,b,c:=dist[i][j],dist[i][k],dist[k][j];
a,b,c:=dist[i][j],dist[i][k],dist[k][j];
if( (a!=Void and b!=Void and c!=Void and a>b+c) or // Inf math
if( (a!=Void and b!=Void and c!=Void and a>b+c) or // Inf math
(a==Void and b!=Void and c!=Void) ){
(a==Void and b!=Void and c!=Void) ){
dist[i][j] = b+c;
dist[i][j] = b+c;
next[i][j] = next[i][k];
next[i][j] = next[i][k];
}
}
}
}
Line 2,354: Line 2,591:
<lang zkl>const V=4;
<lang zkl>const V=4;
dist:=V.pump(List,V.pump(List,Void.copy).copy); // VxV matrix of Void
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 i in (V){ dist[i][i] = 0 } // zero vertexes


/* Graph from the Wikipedia:
/* Graph from the Wikipedia:
Line 2,368: Line 2,605:
dist,next:=FloydWarshallWithPathReconstruction(dist);
dist,next:=FloydWarshallWithPathReconstruction(dist);
println("Shortest distance array:"); printM(dist);
println("Shortest distance array:"); printM(dist);
println("\nPath array:"); printM(next);
println("\nPath array:"); printM(next);
println("\nAll paths:");
println("\nAll paths:");
foreach u,v in (V,V){
foreach u,v in (V,V){
Retrieved from "https://rosettacode.org/wiki/Floyd-Warshall_algorithm"