Floyd-Warshall algorithm: Difference between revisions
m (edit link) |
(J: oops, wasn't actually implementing floyd (result was fine, timing was too slow)) |
||
Line 173: | Line 173: | ||
=={{header|J}}== |
=={{header|J}}== |
||
<lang J> |
<lang J>floyd=: verb define |
||
for_j. i.#y do. |
|||
y=. y <. j ({"1 +/ {) y |
|||
end. |
|||
)</lang> |
|||
Example use: |
Example use: |
||
<lang J>graph=:".;._2]0 :0 |
|||
<lang J> graph=: (_#&.>~1+i.6),&>6{.(#~5 4 3 2 1) </. 7 9 _ _3 14 10 15 _ _5 11 _ 2 6 _ 9 |
|||
_ _ _2 _ NB. 1->3 costs _2 |
|||
⚫ | |||
4 _ 3 _ NB. 2->1 costs 4; 2->3 costs 3 |
|||
_ 7 9 _ _3 14 |
|||
_ _ _ 2 NB. 3->4 costs 2 |
|||
_ _1 _ _ NB. 4->2 costs _1 |
|||
) |
|||
_ _ _ _ 6 _ |
|||
_ _ _ _ _ 9 |
|||
_ _ _ _ _ _ |
|||
(<. <./ .+~)^:_ graph |
|||
_ 7 9 20 _3 2 |
|||
_ _ 10 15 21 _5 |
|||
_ _ _ 11 17 2 |
|||
_ _ _ _ 6 15 |
|||
_ _ _ _ _ 9 |
|||
⚫ | |||
⚫ | |||
<lang J>graph=:".;._2]0 :0 |
|||
The operation <code><./ .+</code> is a matrix inner product, much like <code>+/ .*</code> (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 <code>~</code> conjunction which uses the right argument as a left argument. The result of <code><./ .+~</code> is the shortest "two hop" path between each two nodes in the graph. |
|||
_ _ _2 _ NB. 1->3 costs _2 |
|||
4 _ 3 _ NB. 2->1 costs 4; 2->3 costs 3 |
|||
_ _ _ 2 NB. 3->4 costs 2 |
|||
_ _1 _ _ NB. 4->2 costs _1 |
|||
) |
|||
⚫ | |||
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. |
|||
3 _1 _2 0 |
|||
4 3 2 4 |
|||
5 1 3 2 |
|||
⚫ | |||
⚫ | |||
Finally, we use the inductive operator and ask it to keep repeating this operation until it stops changing (until a result matches its immediately previous argument). [As an aside, note that <code>^:</code> serves the role tail recursion serves in other languages. But it is syntactically distinct from recursion to better show programmer intent.] |
|||
This approach turns out to be faster than the more concise <./ .+~^:_ for many relatively small graphs. |
|||
=={{header|Java}}== |
=={{header|Java}}== |
Revision as of 22:25, 13 April 2016
The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights.
The task: find the lengths of the shortest paths between all pairs of vertices of the given directed graph. Your code may assume that the input has already been checked for loops, parallel edges and negative cycles.
Print the pair, the distance and the path. For instance:
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
- See also
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)
Go
<lang go>package main
import (
"fmt" "math"
)
type arc struct {
to int wt float64
}
func fw(g [][]arc) [][]float64 {
dist := make([][]float64, len(g)) for i := range dist { di := make([]float64, len(g)) for j := range di { di[j] = math.Inf(1) } di[i] = 0 dist[i] = di } for u, arcs := range g { for _, v := range arcs { dist[u][v.to] = v.wt } } for k, dk := range dist { for _, di := range dist { for j, dij := range di { if d := di[k] + dk[j]; dij > d { di[j] = d } } } } return dist
}
func main() {
g := [][]arc{ 1: Template:3, -2, 2: {{1, 4}, {3, 3}}, 3: Template:4, 2, 4: Template:2, -1, } dist := fw(g) for _, d := range dist { fmt.Printf("%4g\n", d) }
}</lang>
- Output:
[ 0 +Inf +Inf +Inf +Inf] [+Inf 0 -1 -2 0] [+Inf 4 0 2 4] [+Inf 5 1 0 2] [+Inf 3 -1 1 0]
J
<lang J>floyd=: verb define
for_j. i.#y do. y=. y <. j ({"1 +/ {) y end.
)</lang>
Example use:
<lang J>graph=:".;._2]0 :0
_ _ _2 _ NB. 1->3 costs _2 4 _ 3 _ NB. 2->1 costs 4; 2->3 costs 3 _ _ _ 2 NB. 3->4 costs 2 _ _1 _ _ NB. 4->2 costs _1
)
<lang J>graph=:".;._2]0 :0
_ _ _2 _ NB. 1->3 costs _2 4 _ 3 _ NB. 2->1 costs 4; 2->3 costs 3 _ _ _ 2 NB. 3->4 costs 2 _ _1 _ _ NB. 4->2 costs _1
)
floyd graph
3 _1 _2 0 4 3 2 4 5 1 3 2 3 _1 1 3</lang>
The graph matrix holds the costs of each directed node. Row index corresponds to starting node. Column index corresponds to ending node. Unconnected nodes have infinite cost.
This approach turns out to be faster than the more concise <./ .+~^:_ for many relatively small graphs.
Java
<lang java>import static java.lang.String.format; import java.util.Arrays;
public class FloydWarshall {
public static void main(String[] args) { int[][] weights = {{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}}; int numVertices = 4;
floydWarshall(weights, numVertices); }
static void floydWarshall(int[][] weights, int numVertices) {
double[][] dist = new double[numVertices][numVertices]; for (double[] row : dist) Arrays.fill(row, Double.POSITIVE_INFINITY);
for (int[] w : weights) dist[w[0] - 1][w[1] - 1] = w[2];
int[][] next = new int[numVertices][numVertices]; for (int i = 0; i < next.length; i++) { for (int j = 0; j < next.length; j++) if (i != j) next[i][j] = j + 1; }
for (int k = 0; k < numVertices; k++) for (int i = 0; i < numVertices; i++) for (int j = 0; j < numVertices; 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) { System.out.println("pair dist path"); for (int i = 0; i < next.length; i++) { for (int j = 0; j < next.length; j++) { if (i != j) { int u = i + 1; int v = j + 1; String path = format("%d -> %d %2d %s", u, v, (int) dist[i][j], u); do { u = next[u - 1][v - 1]; path += " -> " + u; } while (u != v); System.out.println(path); } } } }
}</lang>
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
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>
Racket
<lang racket>#lang typed/racket (require math/array)
- in
- initialized dist and next matrices
- out
- dist and next matrices
- O(n^3)
(define-type Next-T (Option Index)) (define-type Dist-T Real) (define-type Dists (Array Dist-T)) (define-type Nexts (Array Next-T)) (define-type Settable-Dists (Settable-Array Dist-T)) (define-type Settable-Nexts (Settable-Array Next-T))
(: floyd-with-path (-> Index Dists Nexts (Values Dists Nexts))) (: init-edges (-> Index (Values Settable-Dists Settable-Nexts)))
(define (floyd-with-path n dist-in next-in)
(define dist : Settable-Dists (array->mutable-array dist-in)) (define next : Settable-Nexts (array->mutable-array next-in)) (for* ((k n) (i n) (j n)) (when (negative? (array-ref dist (vector j j))) (raise 'negative-cycle)) (define i.k (vector i k)) (define i.j (vector i j)) (define d (+ (array-ref dist i.k) (array-ref dist (vector 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)))) (values dist next))
- utilities
- init random edges costs, matrix 66% filled
(define (init-edges n)
(define dist : Settable-Dists (array->mutable-array (make-array (vector n n) 0))) (define next : Settable-Nexts (array->mutable-array (make-array (vector n n) #f))) (for* ((i n) (j n) #:unless (= i j)) (define i.j (vector i j)) (array-set! dist i.j +Inf.0) (unless (< (random) 0.3) (array-set! dist i.j (add1 (random 100))) (array-set! next i.j j))) (values dist next))
- show path from u to v
(: path (-> Nexts Index Index (Listof Index))) (define (path next u v)
(let loop : (Listof Index) ((u : Index u) (rv : (Listof Index) null)) (if (= u v) (reverse (cons u rv)) (let ((nxt (array-ref next (vector u v)))) (if nxt (loop nxt (cons u rv)) null)))))
- show computed distance
(: mdist (-> Dists Index Index Dist-T)) (define (mdist dist u v)
(array-ref dist (vector u v)))
(module+ main
(define n 8) (define-values (dist next) (init-edges n)) (define-values (dist+ next+) (floyd-with-path n dist next)) (displayln "original dist") dist (displayln "new dist and next") dist+ next+ ;; note, these path and dist calls are not as carefully crafted as ;; the echolisp ones (in fact they're verbatim copied) (displayln "paths and distances") (path next+ 1 3) (mdist dist+ 1 0) (mdist dist+ 0 3) (mdist dist+ 1 3) (path next+ 7 6) (path next+ 6 7))</lang>
- Output:
original dist (mutable-array #[#[0 51 +inf.0 11 44 13 +inf.0 86] #[48 0 70 +inf.0 65 78 77 54] #[29 +inf.0 0 +inf.0 78 14 +inf.0 24] #[40 79 52 0 +inf.0 99 37 88] #[71 62 +inf.0 7 0 +inf.0 +inf.0 +inf.0] #[89 65 83 +inf.0 91 0 41 70] #[69 34 +inf.0 49 +inf.0 89 0 20] #[2 56 +inf.0 60 +inf.0 75 +inf.0 0]]) new dist and next (mutable-array #[#[0 51 63 11 44 13 48 68] #[48 0 70 59 65 61 77 54] #[26 77 0 37 70 14 55 24] #[40 71 52 0 84 53 37 57] #[47 62 59 7 0 60 44 64] #[63 65 83 74 91 0 41 61] #[22 34 85 33 66 35 0 20] #[2 53 65 13 46 15 50 0]]) (mutable-array #[#[#f 1 3 3 4 5 3 3] #[0 #f 2 0 4 0 6 7] #[7 7 #f 7 7 5 5 7] #[0 6 2 #f 0 0 6 6] #[3 1 3 3 #f 3 3 3] #[6 1 2 6 4 #f 6 6] #[7 1 7 7 7 7 #f 7] #[0 0 0 0 0 0 0 #f]]) paths and distances '(1 0 3) 48 11 59 '(7 0 3 6) '(6 7)
Ruby
<lang ruby>class Matrix
def show self.each_slice(self.column_count){|e| puts e.join(" ")} end
def warshall raise "No a valid square" unless self.square? n = self.column_count i = Float::INFINITY short = Matrix.build(n){ i }.to_a n.times do |x| n.times do |y| short[x][y] = 1 if self[x, y] > 0 end short[x][x] = 0 end
n.times do |z| n.times do |x| n.times do |y| short[x][y] = [short[x][y], short[x][z] + short[z][y]].min end end end
short = Matrix.rows(short) end
end</lang>
Tcl
The implementation of Floyd-Warshall in tcllib is quite readable; this example merely initialises a graph from an adjacency list then calls the tcllib code:
<lang Tcl>package require Tcl 8.5 ;# for {*} and [dict] package require struct::graph package require struct::graph::op
struct::graph g
set arclist {
a b a p b m b c c d d e e f f q f g
}
g node insert {*}$arclist
foreach {from to} $arclist {
set a [g arc insert $from $to] g arc setweight $a 1.0
}
set paths [::struct::graph::op::FloydWarshall g]
set paths [dict filter $paths key {a *}] ;# filter for paths starting at "a" set paths [dict filter $paths value {[0-9]*}] ;# whose cost is not "Inf" set paths [lsort -stride 2 -index 1 -real -decreasing $paths] ;# and print the longest first puts $paths</lang>
- Output:
{a q} 6.0 {a g} 6.0 {a f} 5.0 {a e} 4.0 {a d} 3.0 {a m} 2.0 {a c} 2.0 {a p} 1.0 {a b} 1.0 {a a} 0
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)