Skip to main content

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<len; i++){
   for(int j =0; j<len; j++){
    graph[i][j] = INFINITY;
   }
  }
  
  printValue(graph);
  
  
  setvalue(graph, 1, 3, 9);
  setvalue(graph, 1, 2, 7);
  setvalue(graph, 1, 6, 14);
  setvalue(graph, 2, 3, 10);
  setvalue(graph, 2, 4, 15);
  setvalue(graph, 3, 4, 11);
  setvalue(graph, 3, 6, 2);
  setvalue(graph, 4, 5, 6);
  setvalue(graph, 5, 6, 9);
 }
 
 public void setvalue(int [][] graph, int start, int end, int val){
  graph[start][end] = val;
  graph[end][start] = val;
 }
 
 public  void printValue(int graph[][]){
  for(int i=1; i<graph.length; i++){
   for(int j=1; j< graph.length; j++){
    
    String pr = "";
    int val = graph[i][j];
    if(0< val && val < 10){
     pr = "0"+ val; 
    }else{
     if(val == Integer.MAX_VALUE){
      System.out.print("xx");  
      System.out.print(pr + " ");
      continue;
     }
     
     pr = val +"";
    }
    System.out.print(pr + " ");
   }
   System.out.println();
  }
 }
}

if you have any question Comment Please~

Comments

Popular posts from this blog

codefights smooth sailing ( CommonCharacterCount)

https://codefights.com/arcade/intro/level-3/JKKuHJknZNj4YGL32publicstaticintcommonCharacterCount(String s1, String s2) { int sum = 0; char[] as= s1.toCharArray(); char[] bs= s2.toCharArray(); int[] ias = newint[126]; int[] ibs = newint[126]; for (int i = 0; i < as.length; i++) { ias[(int)as[i]]++; } for (int i = 0; i < bs.length; i++) { ibs[(int)bs[i]]++; } for (int i = 0; i < ibs.length; i++) { sum += Math.min(ias[i], ibs[i]); } return sum; }

Given two strings, find the number of common characters between them. Example For s1 = "aabcc" and s2 = "adcaa", the output should be
commonCharacterCount(s1, s2) = 3. Strings have 3 common characters - 2 "a"s and 1 "c". Input/Output [time limit] 3000ms (java)[input] string s1 A string consisting of lowercase latin letters a-z. Guaranteed constraints:
1 ≤ s1.length ≤ 15. [input] string s2 A string consisting of lowercase latin letters a-z. Guaranteed constr…

Bucket Sort in python

I make buckets as many as size of arr
and put data.

arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434] def bucketSort(arr, size): buckets = [[] for i in range(size)] # put arr in bucket for i in range(len(arr)): num = size*arr[i] buckets[int(num)].append(arr[i]) output = [] # use insertion sort for i in range(len(buckets)): insertionSort(buckets[i]) # concat all data for i in range(len(buckets)): while len(buckets[i]) > 0: output.append(buckets[i].pop(0)) return output def swap(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = temp def insertionSort(arr): for i in range(1, len(arr)): index= i print("index : " + str(i)) while index!=0: if arr[index] < arr[index-1]: temp = arr[index] arr[index]= arr[index-1] arr[index-1] = temp index = index-1print(arr) else …