Floyd-Warshall algorithm: Difference between revisions

Content added Content deleted
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
(Add source for Rust)
Line 174:
 
typedef struct{
int sourceVertex, destVertex;
int edgeWeight;
}edge;
 
typedef struct{
int vertices, edges;
edge* edgeMatrix;
}graph;
 
graph loadGraph(char* fileName){
FILE* fp = fopen(fileName,"r");
graph G;
int i;
fscanf(fp,"%d%d",&G.vertices,&G.edges);
G.edgeMatrix = (edge*)malloc(G.edges*sizeof(edge));
for(i=0;i<G.edges;i++)
fscanf(fp,"%d%d%d",&G.edgeMatrix[i].sourceVertex,&G.edgeMatrix[i].destVertex,&G.edgeMatrix[i].edgeWeight);
fclose(fp);
return G;
}
 
void floydWarshall(graph g){
int processWeights[g.vertices][g.vertices], processedVertices[g.vertices][g.vertices];
int i,j,k;
for(i=0;i<g.vertices;i++)
for(j=0;j<g.vertices;j++){
processWeights[i][j] = SHRT_MAX;
processedVertices[i][j] = (i!=j)?j+1:0;
}
}
for(i=0;i<g.edges;i++)
processWeights[g.edgeMatrix[i].sourceVertex-1][g.edgeMatrix[i].destVertex-1] = g.edgeMatrix[i].edgeWeight;
for(i=0;i<g.vertices;i++)
for(j=0;j<g.vertices;j++)
for(k=0;k<g.vertices;k++){
if(processWeights[j][i] + processWeights[i][k] < processWeights[j][k]){
processWeights[j][k] = processWeights[j][i] + processWeights[i][k];
processedVertices[j][k] = processedVertices[j][i];
}
}
}
}
printf("pair dist path");
for(i=0;i<g.vertices;i++)
for(j=0;j<g.vertices;j++){
if(i!=j){
printf("\n%d -> %d %3d %5d",i+1,j+1,processWeights[i][j],i+1);
k = i+1;
do{
do{
k = processedVertices[k-1][j];
printf("->%d",k);
}while(k!=j+1);
}
}
}
}
}
 
int main(int argC,char* argV[]){
if(argC!=2)
printf("Usage : %s <file containing graph data>");
else
floydWarshall(loadGraph(argV[1]));
return 0;
}
</lang>
Line 529:
 
(define (floyd-with-path n dist next (d 0))
(for* ((k n) (i n) (j n))
#:break (< (array-ref dist j j) 0) => 'negative-cycle
(set! d (+ (array-ref dist i k) (array-ref dist k j)))
(when (< d (array-ref dist i j))
(array-set! dist i j d)
(array-set! next i j (array-ref next i k)))))
 
;; utilities
Line 541:
(define (init-edges n dist next)
(for* ((i n) (j n))
(array-set! dist i i 0)
(array-set! next i j null)
#:continue (= j i)
(array-set! dist i j Infinity)
#:continue (< (random) 0.3)
(array-set! dist i j (1+ (random 100)))
(array-set! next i j j)))
 
;; show path from u to v
(define (path u v)
(cond
((= u v) (list u))
((null? (array-ref next u v)) null)
(else (cons u (path (array-ref next u v) v)))))
 
(define( mdist u v) ;; show computed distance
(array-ref dist u v))
(define (task)
(init-edges n dist next)
(array-print dist) ;; show init distances
(floyd-with-path n dist next))
</lang>
{{out}}
Line 904:
{{out}}
<pre>
pair dist 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>
 
Line 1,252:
reduce $nodes[] as $u (.;
reduce $nodes[] as $v (.;
(.[$u][$w] + .[$w][$v]) as $x
| if .[$u][$v] > $x then .[$u][$v] = $x
else . end )))
;
 
Line 1,577:
=={{header|Perl}}==
<lang perl6>sub FloydWarshall{
my $edges = shift;
my (@dist, @seq);
my $num_vert = 0;
# insert given dists into dist matrix
map {
$dist[$_->[0] - 1][$_->[1] - 1] = $_->[2];
$num_vert = $_->[0] if $num_vert < $_->[0];
$num_vert = $_->[1] if $num_vert < $_->[1];
} @$edges;
my @vertices = 0..($num_vert - 1);
# init sequence/"next" table
for my $i(@vertices){
for my $j(@vertices){
$seq[$i][$j] = $j if $i != $j;
}
}
}
}
# diagonal of dists matrix
#map {$dist[$_][$_] = 0} @vertices;
for my $k(@vertices){
for my $i(@vertices){
next unless defined $dist[$i][$k];
for my $j(@vertices){
next unless defined $dist[$k][$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];
$seq[$i][$j] = $seq[$i][$k];
}
}
}
}
}
}
}
}
# print table
print "pair dist path\n";
for my $i(@vertices){
for my $j(@vertices){
next if $i == $j;
my @path = ($i + 1);
while($seq[$path[-1] - 1][$j] != $j){
push @path, $seq[$path[-1] - 1][$j] + 1;
}
}
push @path, $j + 1;
printf "%d -> %d %4d %s\n",
$path[0], $path[-1], $dist[$i][$j], join(' -> ', @path);
}
}
}
}
}
 
Line 2,089:
4 -> 2 -1 4 -> 2
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>
 
Line 2,159 ⟶ 2,396:
{{trans|Ruby}}
<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) }
for u,v,w in edge {
Line 2,172 ⟶ 2,409:
}
}
 
var summary = "pair dist path\n"
for i,j (^n ~X ^n) {
Line 2,178 ⟶ 2,415:
var u = i
var path = [u]
while (u  != j) {
path << (u = nxt[u][j])
}
path.map!{|u| u+1 }.join!(" -> ")
summary += ("%d ->  %d   %4d   %s\n" % (i+1, j+1, dist[i][j], path))
}
 
Line 2,337 ⟶ 2,574:
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
(a==Void and b!=Void and c!=Void) ){
dist[i][j] = b+c;
next[i][j] = next[i][k];
}
}
Line 2,354 ⟶ 2,591:
<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
 
/* Graph from the Wikipedia:
Line 2,368 ⟶ 2,605:
dist,next:=FloydWarshallWithPathReconstruction(dist);
println("Shortest distance array:"); printM(dist);
println("\nPath array:"); printM(next);
println("\nAll paths:");
foreach u,v in (V,V){
Retrieved from "https://rosettacode.org/wiki/Floyd-Warshall_algorithm"