## Wednesday, January 21, 2015

### Floyd-Warshall's algorithm

Before starting to explain Floyd algorithm,  I want to compare Dijkstra algorithm with Floyd.

1. it is used only when we already know start node to all nodes
this means that source node should be single.
2. It will fail if graph has negative distance. distance or weight should be > 0
3. it is also called single-source shortest path or SSSP algorithm.
4.  O(N^2)

Floyd-Warshall's algorithm

1. it is used to find all nodes to all nodes
2. This only fails when there are negative cycles.
3.  O(N^3)
4. We can have one or more links of negative cost, c(x, y)<0,

Later on, I will Study Bellman-Ford  and also post on blog.

```1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j]
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if```

Code Explanation

1. line 3, define graph and initialize value. in my case Integer.max
2. line 5, set real weight of edge between two nodes.
3. find dist[i][j] through k node. .. repeatedly k = 1 to last node
find and set if dist[i][j] < dist[i][k] + dist[k][j], in other words, find minimum path and update minimum distance

Picture Explanation

continue and continue.....
.............
.......
...
.

Finally we get shorted graph from all nodes to all node

Last time, I wrote about shortest path by using dijkstra, with above graph.
at that time,  test case was 1 to 5 , and result is 20.
and also this result by using floyd is  the same as using dijkstra.

below is my java code

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96``` ```package mybook; import java.util.Arrays; public class FloydWarshall { public int[][] graph ; public final int INFINITY =Integer.MAX_VALUE; public static void main(String[] args) { // TODO Auto-generated method stub FloydWarshall floyd = new FloydWarshall(); floyd.init(); floyd.printValue(floyd.graph); floyd.start(); System.out.println(); floyd.printValue(floyd.graph); } private void start() { for(int k=1; k<7; k++){ for(int i=1; i<7; i++){ for(int j=1; j<7; j++){ if(graph[i][k]!= INFINITY && graph[k][j] != INFINITY && i != j){ System.out.println(); System.out.println("from : " + i + ", center : " + k + ", to : " + j); if(graph[i][j] > graph[i][k] + graph[k][j]){ graph[i][j] = graph[i][k] + graph[k][j]; } //System.out.println("[" +i + "]["+j +"] : " + graph[i][j] ); printValue(graph); } } } } } public void init(){ int count = 7; graph = new int [count][count]; printValue(graph); int len =graph.length; for(int i=0; i

if you have any question Comment Please~