Floyd-Warshall algorithm

Floyd-Warshall algorithm is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights.

EchoLisp

Transcription of the Floyd-Warshall algorithm, with best path computation. <lang scheme> (lib 'matrix)

in

initialized dist and next matrices

out

dist and next matrices

O(n^3)

(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

init random edges costs, matrix 66% filled

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

Output:

(task)

  0    Infinity   Infinity   13         98         Infinity   35         47       
  8    0          Infinity   Infinity   83         77         16         3        
  73   3          0          3          76         84         91         Infinity 
  30   49         Infinity   0          41         Infinity   4          4        
  22   83         92         Infinity   0          30         27         98       
  6    Infinity   Infinity   24         59         0          Infinity   Infinity 
  60   Infinity   45         Infinity   67         100        0          Infinity 
  72   15         95         21         Infinity   Infinity   27         0        


(array-print dist) ;; computed distances

  0    32   62   13   54   84   17   17 
  8    0    61   21   62   77   16   3  
  11   3    0    3    44   74   7    6  
  27   19   49   0    41   71   4    4  
  22   54   72   35   0    30   27   39 
  6    38   68   19   59   0    23   23 
  56   48   45   48   67   97   0    51 
  23   15   70   21   62   92   25   0  

(path 1 3)  → (1 0 3)
(mdist 1 0) → 8
(mdist 0 3) → 13
(mdist 1 3) → 21 ;; = 8 + 13
(path 7 6) → (7 3 6)
(path 6 7) → (6 2 1 7)

J

<lang J>(<. <./ .+/~)^:_</lang>

Example use:

<lang J> graph=: (_#&.>~1+i.6),&>6{.(#~5 4 3 2 1) </. 7 9 _ _3 14 10 15 _ _5 11 _ 2 6 _ 9

  graph

_ 7 9 _ _3 14 _ _ 10 15 _ _5 _ _ _ 11 _ 2 _ _ _ _ 6 _ _ _ _ _ _ 9 _ _ _ _ _ _

  (<.   <./ .+/~)^:_ graph

_ 7 9 20 _3 2 _ _ 10 15 21 _5 _ _ _ 11 17 2 _ _ _ _ 6 15 _ _ _ _ _ 9 _ _ _ _ _ _</lang>

The graph matrix holds the costs of each directed node. Row index is index of starting node. Column index is index of ending node. Unconnected nodes have infinite cost.

JavaScript

<lang javascript>var graph = []; for (i = 0; i < 10; ++i) {

 graph.push([]);
 for (j = 0; j < 10; ++j)
   graph[i].push(i == j ? 0 : 9999999);

}

for (i = 1; i < 10; ++i) {

 graph[0][i] = graph[i][0] = parseInt(Math.random() * 9 + 1);

}

for (k = 0; k < 10; ++k) {

 for (i = 0; i < 10; ++i) {
   for (j = 0; j < 10; ++j) {
     if (graph[i][j] > graph[i][k] + graph[k][j])
       graph[i][j] = graph[i][k] + graph[k][j]
   }
 }

}

console.log(graph);</lang>

PHP

<lang php><?php $graph = array(); for ($i = 0; $i < 10; ++$i) {

   $graph[] = array();
   for ($j = 0; $j < 10; ++$j)
       $graph[$i][] = $i == $j ? 0 : 9999999;

}

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

   $graph[0][$i] = $graph[$i][0] = rand(1, 9);

}

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

   for ($i = 0; $i < 10; ++$i) {
       for ($j = 0; $j < 10; ++$j) {
           if ($graph[$i][$j] > $graph[$i][$k] + $graph[$k][$j])
               $graph[$i][$j] = $graph[$i][$k] + $graph[$k][$j];
       }
   }

}

print_r($graph); ?></lang>

Ruby

<lang ruby>require 'matrix'

graph = [] 10.times{|i| graph[i] = [].fill(9999999, 0, 10)} 10.times{|i| graph[i][i] = 0} (1..9).each{|i| graph[i][0] = graph[0][i] = Random.rand(9) + 1}

10.times do |k|

 10.times do |i|
   10.times do |j|
     graph[i][j] = graph[i][k] + graph[k][j] if graph[i][j] > graph[i][k] + graph[k][j]
   end
 end

end

puts Matrix[graph]</lang>