Floyd-Warshall algorithm, a formula consisting of the core is very simple. A, B, C, I suppose we have 3 points. In this case, the shortest distance between A and C (distance (A, C), distance (A, B) + distance (B, C)) is up. Floyd-Warshall’ı need to apply to a table. The size of this table, depending on the number of points to be determined. We got one point, the table size N * N N
int[,] table = new int[5,5];
On the basis of the algorithm used for the function of the input for this table are the values at the maximum. The distance of each point of self-0, the distance to other points, we will begin by accepting the infinite.
int INFINITY = 9999999; int N = 5; for (int i = 0; i < N; i++) for(int j = 0; j < N; j++) table[i,j] = i == j ? 0 : INFINITY;
After this operation, the value of the table will be as follows.
Second, to keep the connection between the points and to build the matrix of contiguity for questioning. If you have an edge from one point to another entry in the table that would give a value. For example, point 3 and point 4, one side has 2 points. Therefore, our statements [2,3] = [2.4] = 1 = [3.2] = [4.2]. Grafımız no way we obtain for the diagonal matrix based on contiguity should be symmetrical. 1 to 4, because to have the edge in the 4 to 1, this also means there are also edges. Our example is a way you could tell it had graphs. After this, the final version of the table will be as follows:
Floyd-Warshall can now apply the formula:
for( int k = 0; k < N; k++) for( int i = 0; i < N; i++) for( int j = 0; j < N; j++) table[i,j] = Math.Min(table[i,j], table[i,k] + table[k,j]);
That’s it. After this, our table will be as final.
Now using the table between the two points (a, b) can query the shortest distance. table [a, b] = table [b, a].