Floyd-Warshall algorithm: Difference between revisions

Content added Content deleted

Inline

Revision as of 05:01, 11 October 2015

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:

(define n 8)
(define next (make-array n n))
(define dist (make-array n n))
(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

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.

The operation <./ .+ is a matrix inner product, much like +/ .* (which is the classic "matrix inner product" or "dot product" or "matrix multiply" -- each row from the left argument is multiplied - column-wise - with the right argument and then those columns are each summed and the resulting rows form rows of the result). But we replace addition in the classic dot product with a minimum value function, and we replace multiplication in the classic dot product with addition. We then derive a new version of this operation with the ~ conjunction which uses the right argument as a left argument. The result of <./ .+~ is the shortest "two hop" path between each two nodes in the graph.

We then combine that result with the original result using the phrase (<. <./ .+~). In other words, this is the shortest one or two hop path between any two points in our graph.

Finally, we use the inductive operator and ask it to keep repeating this operation until it stops changing (until a result matches a previous argument).

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>

zkl

<lang zkl>fcn FloydWarshallWithPathReconstruction(dist){ // dist is munged

  V:=dist[0].len();
  next:=V.pump(List,V.pump(List,Void.copy).copy);  // VxV matrix of Void
  foreach u,v in (V,V){ if(dist[u][v]!=Void and u!=v) next[u][v] = v }
  foreach k,i,j in (V,V,V){
     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];

     }
  }
  return(dist,next)

} fcn path(next,u,v){

  if(Void==next[u][v]) return(T);
  path:=List(u);
  while(u!=v){ path.append(u = next[u][v]) }
  path

} fcn printM(m){ m.pump(Console.println,rowFmt) } fcn rowFmt(row){ ("%5s "*row.len()).fmt(row.xplode()) }</lang> <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:

  1  2  3  4
d ----------

1| 0 X -2 X 2| 4 0 3 X 3| X X 0 2 4| X -1 X 0

/

dist[0][2]=-2; dist[1][0]=4; dist[1][2]=3; dist[2][3]=2; dist[3][1]=-1;

dist,next:=FloydWarshallWithPathReconstruction(dist); println("Shortest distance array:"); printM(dist); println("\nPath array:"); printM(next); println("\nAll paths:"); foreach u,v in (V,V){

  if(p:=path(next,u,v)) p.println();

}</lang>

Output:

Shortest distance array:
    0    -1    -2     0 
    4     0     2     4 
    5     1     0     2 
    3    -1     1     0 

Path array:
 Void     2     2     2 
    0  Void     0     0 
    3     3  Void     3 
    1     1     1  Void 

All paths:
L(0,2,3,1)
L(0,2)
L(0,2,3)
L(1,0)
L(1,0,2)
L(1,0,2,3)
L(2,3,1,0)
L(2,3,1)
L(2,3)
L(3,1,0)
L(3,1)
L(3,1,0,2)

@@ Line 115: / Line 115: @@
 We then combine that result with the original result using the phrase <code>(<. <./ .+~)</code>. In other words, this is the shortest one or two hop path between any two points in our graph.
-Finally, we use the inductive operator and ask it to keep repeating this operation until it stops changing (until the result matches the previous argument).
+Finally, we use the inductive operator and ask it to keep repeating this operation until it stops changing (until a result matches a previous argument).
 =={{header|JavaScript}}==