Floyd Warshall

Standard

Add to DiggAdd to FaceBookAdd to Google BookmarkAdd to MySpaceAdd to Twitter

There are many notable algorithms to calculate the shortest path between vertices in a graph. Most are based on single source to a set of destination vertices. Examples of such famous algorithms include Dijkstra’s, Bellman-Ford and even Breadth First Search for weightless graphs. However, sometimes we wish to calculate the shortest paths between all pairs of vertices. An easy way to calculate this is to loop through each possible pair of vertices and run a Dijkstra through it. However, there exists a more efficient way to calculate this in n^3 time complexity.

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.

table 1 2 3 4 5
1 0 INF INF INF INF
2 INF 0 INF INF INF
3 INF INF 0 INF INF
4 INF INF INF 0 INF
5 INF INF INF INF 0

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:

table 1 2 3 4 5
1 0 INF INF 1 INF
2 INF 0 1 1 INF
3 INF 1 0 1 INF
4 1 1 1 0 1
5 INF INF INF 1 0

Floyd-Warshall can now apply the formula:

for( int k = 0; k &lt; N; k++)
for( int i = 0; i &lt; N; i++)
for( int j = 0; j &lt; 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.

table 1 2 3 4 5
1 0 2 2 1 2
2 2 0 1 1 2
3 2 1 0 1 2
4 1 1 1 0 1
5 2 2 2 1 0

Now using the table between the two points (a, b) can query the shortest distance. table [a, b] = table [b, a].

Advertisements

atod function

Standard

Add to DiggAdd to FaceBookAdd to Google BookmarkAdd to MySpaceAdd to Twitter
atod function’s work is identical to atoi‘s. But this one is for doubles

// for texting/ example purposes
#include <iostream> // for cout and endl
#include <cmath> // for pow
using namespace std; // so we don't have to do std::coud or std::endl
//end testing/ example purposes 

char* substr(char* str, int start, int end){
	char* a = new char[1+(end-start)]; // we need a new char array for the return
	for(int i=start; i<end; i++){ // loop through the string
		a[i-start] = str[i]; // set the characters in the new char array to those from the old one compensating for the substring
	}
	a[end-start] = '\0'; // add the null character, so we can output
	return a; // return
}

double atod(char* a){
	double retVal = atoi(a); // start off getting the number, assuming it is a valid string to use atoi on.
	int start = 0;
	int end = 0;
	for(int i=0; a[i] != '\0'; i++){ // loop through the string to find the positions of the decimal portion, if there is one
		if(a[i] == '.' && start == 0){
			start = i+1; // set the start position to 1 more than the current (avoids a char as the first character - we want a digit)
		}
		else if(start != 0 &&  (a[i] < '0' || a[i] > '9')){ // make sure that start is set and that we aren't looking at digits
			end = i; // if so, set the end location for the substring
			break; // we don't need to continue anymore - break out of the loop
		}
	}
	if(end > start){ // avoids substring problems.
		char* decimal = substr(a, start, end); // get the string that is after the decimal point
		int dec = atoi(decimal); // make it an integer
		int power = end-start; // find the power of 10 we need to divide by
		retVal += ((double)dec)/(pow(10.0, (double)power)); // divide and add to the return value (thus making it a true double)
	}
	return retVal; // return - simple enough
}

// for testing/ example purposes
int main(){
	cout << atod("127.02501 test") << endl; // test it out on a valid character stream
	return 0;
}
// end testing/ example purposes