Floyd's algorithm - Revision history

David Eppstein: double redir

2007-06-17T18:59:36Z

double redir

← Previous revision		Revision as of 18:59, 17 June 2007
Line 1:		Line 1:
	#REDIRECT [[~~Floyd-Warshall~~ algorithm]]		#REDIRECT [[Floyd–Warshall algorithm]]

Abdull at 10:33, 9 March 2006

2006-03-09T10:33:35Z

← Previous revision		Revision as of 10:33, 9 March 2006
Line 1:		Line 1:
			#REDIRECT [[Floyd-Warshall algorithm]]
	'''Floyd's algorithm''' is a O(n^3) algorithm to find the [[shortest path]] between all pairs of [[node]]s in a [[graph]]. It was developed by [[Robert W Floyd]].

	==See also==
	* [[Dijkstra's algorithm]]
	Floyd's Algorithm - Shortest Paths
	This algorithm is designed to find the least-expensive paths between all the vertices in a graph. It does this by operating on a matrix representing the costs of edges between vertices.
	Before we invoke Floyd's algorithm we must build a matrix, usually in a two-dimensional array. If there are n vertices in our graph, our matrix will be nxn. Each row in the matrix represents a "starting" vertex in the graph while each column in the matrix represents an "ending" point in the graph. If there is an edge between a starting point i and ending point j in the graph, the cost of this edge is placed in position (i,j) of the matrix. If we are dealing with an undirected graph in which all edges are bi-directional, an entry is also made in position (j,i) of the matrix. If there is no edge directly linking two vertices, an infinite (or, in practice, very large) value is placed in the (i,j) position of the matrix to specify that it is impossible to directly move from i to j.

	For example, if we have a graph in which points 1 and 5 are connected by a bi-directional edge with a cost of 22 units, we would place the number 22 into positions (1,5) and (5,1) of our matrix.

	Once we have set this matrix up, we use Floyd's algorithm to compute the shortest distance between all points in the graph.

	==Implementation==
	Floyd's algorithm is given below in C:

	int floyds(int *matrix) {
	int k, i, j;

	for (k = 0; k < n; k++)
	for (i = 0; i < n; i++)
	for (j = 0; j < n; j++)
	if (matrix[i][j] > (matrix[i][k] + matrix[k][j]))
	matrix[i][j] = matrix[i][k] + matrix[k][j];
	}



	When this routine finishes the entries in all positions of the matrix represent the lowest-cost traversal between the row-vertex and column-vertex.

	Floyd's algorithm works by looking for all non-direct paths between two vertices that have a less-expensive total cost than the best way yet found to move between said vertices. If such a path is found, it becomes the value against which future indirect paths between these vertices are tested. In the end, each element of the matrix represents the lowest-cost traversal between the vertices it's row and column represent. Remember that if the graph is directed, so is the answer in (i,j) of the matrix; moreover, (i,j) may not be equal to (j,i) in a digraph([[directed graph]]).

	It is clear that Floyd's algorithm takes <math>n^3</math> time.

	==Dangers of Floyd's Algorithm==

	Floyd's algorithm does not work if there is a negative weight cycle.

	[[Category:Algorithms]]

128.208.246.64 at 23:21, 14 February 2006

2006-02-14T23:21:00Z

← Previous revision		Revision as of 23:21, 14 February 2006
Line 31:		Line 31:

	It is clear that Floyd's algorithm takes <math>n^3</math> time.		It is clear that Floyd's algorithm takes <math>n^3</math> time.

			==Dangers of Floyd's Algorithm==

			Floyd's algorithm does not work if there is a negative weight cycle.

	[[Category:Algorithms]]		[[Category:Algorithms]]

Sartak: Arrays in C are 0-based, not 1-based.

2006-01-31T07:12:38Z

Arrays in C are 0-based, not 1-based.

← Previous revision		Revision as of 07:12, 31 January 2006
Line 17:		Line 17:
	int k, i, j;		int k, i, j;

	for (k = 1; k <= n; k++)		for (k = 0; k < n; k++)
	for (i = 1; i <= n; i++)		for (i = 0; i < n; i++)
	for (j = 1; j <= n; j++)		for (j = 0; j < n; j++)
	if (matrix[i][j] > (matrix[i][k] + matrix[k][j]))		if (matrix[i][j] > (matrix[i][k] + matrix[k][j]))
	matrix[i][j] = matrix[i][k] + matrix[k][j];		matrix[i][j] = matrix[i][k] + matrix[k][j];

134.39.100.5: /* Implementation */

2006-01-13T03:33:02Z

Implementation

← Previous revision		Revision as of 03:33, 13 January 2006
Line 21:		Line 21:
	for (j = 1; j <= n; j++)		for (j = 1; j <= n; j++)
	if (matrix[i][j] > (matrix[i][k] + matrix[k][j]))		if (matrix[i][j] > (matrix[i][k] + matrix[k][j]))
	matrix[i,j] = matrix[i][k] + matrix[k][j];		matrix[i][j] = matrix[i][k] + matrix[k][j];
	}		}

200.167.86.146 at 22:17, 22 November 2005

2005-11-22T22:17:36Z

← Previous revision		Revision as of 22:17, 22 November 2005
Line 28:		Line 28:
	When this routine finishes the entries in all positions of the matrix represent the lowest-cost traversal between the row-vertex and column-vertex.		When this routine finishes the entries in all positions of the matrix represent the lowest-cost traversal between the row-vertex and column-vertex.

	Floyd's algorithm works by looking for all non-direct paths between two vertices that have a less-expensive total cost than the best way yet found to move between said vertices. If such a path is found, it becomes the value against which future indirect paths between these vertices are tested. In the end, each element of the matrix represents the lowest-cost traversal between the vertices it's row and column represent. Remember that if the graph is directed, so is the answer in (i,j) of the matrix; moreover, (i,j) may not be equal to (j,i) in a ~~di-~~graph.		Floyd's algorithm works by looking for all non-direct paths between two vertices that have a less-expensive total cost than the best way yet found to move between said vertices. If such a path is found, it becomes the value against which future indirect paths between these vertices are tested. In the end, each element of the matrix represents the lowest-cost traversal between the vertices it's row and column represent. Remember that if the graph is directed, so is the answer in (i,j) of the matrix; moreover, (i,j) may not be equal to (j,i) in a digraph([[directed graph]]).

	It is clear that Floyd's algorithm takes <math>n^3</math> time.		It is clear that Floyd's algorithm takes <math>n^3</math> time.

24.141.218.183 at 21:26, 13 November 2005

2005-11-13T21:26:37Z

← Previous revision		Revision as of 21:26, 13 November 2005
Line 30:		Line 30:
	Floyd's algorithm works by looking for all non-direct paths between two vertices that have a less-expensive total cost than the best way yet found to move between said vertices. If such a path is found, it becomes the value against which future indirect paths between these vertices are tested. In the end, each element of the matrix represents the lowest-cost traversal between the vertices it's row and column represent. Remember that if the graph is directed, so is the answer in (i,j) of the matrix; moreover, (i,j) may not be equal to (j,i) in a di-graph.		Floyd's algorithm works by looking for all non-direct paths between two vertices that have a less-expensive total cost than the best way yet found to move between said vertices. If such a path is found, it becomes the value against which future indirect paths between these vertices are tested. In the end, each element of the matrix represents the lowest-cost traversal between the vertices it's row and column represent. Remember that if the graph is directed, so is the answer in (i,j) of the matrix; moreover, (i,j) may not be equal to (j,i) in a di-graph.

	It is clear that Floyd's algorithm takes n3 time.		It is clear that Floyd's algorithm takes <math>n^3</math> time.

	[[Category:Algorithms]]		[[Category:Algorithms]]

213.6.123.36: /* Implementation */

2005-11-01T16:54:44Z

Implementation

← Previous revision		Revision as of 16:54, 1 November 2005
Line 14:		Line 14:
	Floyd's algorithm is given below in C:		Floyd's algorithm is given below in C:

	int floyds(int *matrix) {		int floyds(int *matrix) {
	int k, i, j;		int k, i, j;


	for (k = 1; k <= n; k++)		for (k = 1; k <= n; k++)
	for (i = 1; i <= n; i++)		for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)		for (j = 1; j <= n; j++)
	if (matrix[i][j] > (matrix[i][k] + matrix[k][j]))		if (matrix[i][j] > (matrix[i][k] + matrix[k][j]))
	matrix[i,j] = matrix[i][k] + matrix[k][j];		matrix[i,j] = matrix[i][k] + matrix[k][j];
	}		}

Ruud Koot at 17:45, 13 October 2005

2005-10-13T17:45:00Z

← Previous revision		Revision as of 17:45, 13 October 2005
Line 9:		Line 9:
	For example, if we have a graph in which points 1 and 5 are connected by a bi-directional edge with a cost of 22 units, we would place the number 22 into positions (1,5) and (5,1) of our matrix.		For example, if we have a graph in which points 1 and 5 are connected by a bi-directional edge with a cost of 22 units, we would place the number 22 into positions (1,5) and (5,1) of our matrix.

	Once we have set this matrix up, we use Floyd's algorithm to compute the shortest distance between all points in the graph. ~~Floyd's algorithm is given below in C:~~		Once we have set this matrix up, we use Floyd's algorithm to compute the shortest distance between all points in the graph.

			==Implementation==

			Floyd's algorithm is given below in C:

	--------------------------------------------------------------------------------

	int floyds(int *matrix) {		int floyds(int *matrix) {
Line 26:		Line 25:


	--------------------------------------------------------------------------------

	When this routine finishes the entries in all positions of the matrix represent the lowest-cost traversal between the row-vertex and column-vertex.		When this routine finishes the entries in all positions of the matrix represent the lowest-cost traversal between the row-vertex and column-vertex.
Line 33:		Line 31:

	It is clear that Floyd's algorithm takes n3 time.		It is clear that Floyd's algorithm takes n3 time.

			[[Category:Algorithms]]

210.1.94.209: /* See also */

2005-10-10T22:35:13Z

← Previous revision		Revision as of 22:35, 10 October 2005
Line 32:		Line 32:
	Floyd's algorithm works by looking for all non-direct paths between two vertices that have a less-expensive total cost than the best way yet found to move between said vertices. If such a path is found, it becomes the value against which future indirect paths between these vertices are tested. In the end, each element of the matrix represents the lowest-cost traversal between the vertices it's row and column represent. Remember that if the graph is directed, so is the answer in (i,j) of the matrix; moreover, (i,j) may not be equal to (j,i) in a di-graph.		Floyd's algorithm works by looking for all non-direct paths between two vertices that have a less-expensive total cost than the best way yet found to move between said vertices. If such a path is found, it becomes the value against which future indirect paths between these vertices are tested. In the end, each element of the matrix represents the lowest-cost traversal between the vertices it's row and column represent. Remember that if the graph is directed, so is the answer in (i,j) of the matrix; moreover, (i,j) may not be equal to (j,i) in a di-graph.

			It is clear that Floyd's algorithm takes n3 time.
	It is clear that Floyd's algorithm takes n3 time. In the next section we will discuss an alternative to Floyd's algorithm called Dijkstra's algorithm. It is important to note, however, that for dense graphs (i.e. graphs with many edges) Floyd's algorithm is as good as or better than Dijkstra's algorithm.