Floyd algorithm implementation ideas and example code
- 2020-04-02 02:09:05
- OfStack
As we know, the Floyd algorithm is used to find shortest paths. Floyd algorithm can be said to be an extension of Warshall algorithm, three for loops can solve the problem, so its time complexity is O(n^3).
The basic idea of Floyd algorithm is as follows: the shortest path from any node A to any node B is no more than two possibilities, 1 is directly from A to B, 2 is from A through A number of nodes X to B. So, we assume that Dis(AB) is the shortest path distance from node A to node B. For each node X, we check Dis(AX) + Dis(XB). < Is Dis(AB) true? If so, prove that the path from A to X to B is shorter than the path from A directly to B, then we set Dis(AB) = Dis(AX) + Dis(XB). In this way, when we have traversed all nodes X, the shortest path distance from A to B is recorded in Dis(AB).
Simple enough, the code might look like this:
for ( int i = 0; i < Number of nodes ; ++i )
{
for ( int j = 0; j < Number of nodes ; ++j )
{
for ( int k = 0; k < Number of nodes ; ++k )
{
if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )
{
//Find a shorter path
Dis[i][j] = Dis[i][k] + Dis[k][j];
}
}
}
}
But here we have to pay attention to the nested order of the loop, if we put all the check nodes X in the innermost layer, then the result will not be correct, why? Because then the shortest path from I to j is determined too soon, and when there is a shorter path, it will not be updated.
Let's take a look at an example, as shown below:
< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201401/2014122153914312.png" >
The red Numbers in the figure represent edge weights. If we check all nodes X in the innermost layer, then for A minus
>
B, we can only find one path, which is A minus
>
B, the path distance is 9. And that's clearly not true, the true shortest path is A minus
>
D -
>
C -
>
B, the path distance is 6. The reason for the error is that we put all the check nodes X in the innermost layer, causing us to determine the shortest path from A to B too soon, when we determine A minus
>
For the shortest path of B, Dis(AC) has not been calculated. Therefore, we need to rewrite the loop order as follows:
for ( int k = 0; k < Number of nodes ; ++k )
{
for ( int i = 0; i < Number of nodes ; ++i )
{
for ( int j = 0; j < Number of nodes ; ++j )
{
if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )
{
//Find a shorter path
Dis[i][j] = Dis[i][k] + Dis[k][j];
}
}
}
}
So for each node X, we're going to process all the I's to j's before we go on to the next node.
So the next question is, how do we find the shortest path? We need an auxiliary array Path, which works like this: if the value of Path(AB) is P, then the shortest Path from A to B is A- > . - > P - > B. So let's say we're looking for A minus > The shortest Path of B, so let's look for that, and let's say that Path(AB) is P, and then let's look for Path(AP), and let's say that Path(AP) is L, and then let's look for Path(AL), and let's say that Path(AL) is A, and then let's say that the shortest Path is A minus > L - > P - > B.
So, how do I fill in the value of Path? Very simply, when we find Dis of AX plus Dis of XB. < When Dis (AB) is true, you change the shortest path to A minus > . - > X - > . - > B, and at this point, the value of Path of XB is known, so Path of AB is equal to Path of XB.
Ok, so the basic introduction is done, and now it's time to implement, here we use the graph and the adjacency matrix:
#define INFINITE 1000 //The maximum
#define MAX_VERTEX_COUNT 20 //Maximum number of vertices
//////////////////////////////////////////////////////////////////////////
struct Graph
{
int arrArcs[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT]; //Adjacency matrix
int nVertexCount; //Vertex number
int nArcCount; //The number of edges
};
//////////////////////////////////////////////////////////////////////////
First, we write a method to read the data into the graph:
void readGraphData( Graph *_pGraph )
{
std::cout << " Please enter the number of vertices and the number of edges : ";
std::cin >> _pGraph->nVertexCount;
std::cin >> _pGraph->nArcCount;
std::cout << " Please enter the adjacency matrix data :" << std::endl;
for ( int row = 0; row < _pGraph->nVertexCount; ++row )
{
for ( int col = 0; col < _pGraph->nVertexCount; ++col )
{
std::cin >> _pGraph->arrArcs[row][col];
}
}
}
Next, the core Floyd algorithm:
void floyd( int _arrDis[][MAX_VERTEX_COUNT], int _arrPath[][MAX_VERTEX_COUNT], int _nVertexCount )
{
//First, initialize _arrPath
for ( int i = 0; i < _nVertexCount; ++i )
{
for ( int j = 0; j < _nVertexCount; ++j )
{
_arrPath[i][j] = i;
}
}
//////////////////////////////////////////////////////////////////////////
for ( int k = 0; k < _nVertexCount; ++k )
{
for ( int i = 0; i < _nVertexCount; ++i )
{
for ( int j = 0; j < _nVertexCount; ++j )
{
if ( _arrDis[i][k] + _arrDis[k][j] < _arrDis[i][j] )
{
//Find a shorter path
_arrDis[i][j] = _arrDis[i][k] + _arrDis[k][j];
_arrPath[i][j] = _arrPath[k][j];
}
}
}
}
}
OK, finally, the output data code:
void printResult( int _arrDis[][MAX_VERTEX_COUNT], int _arrPath[][MAX_VERTEX_COUNT], int _nVertexCount )
{
std::cout << "Origin -> Dest Distance Path" << std::endl;
for ( int i = 0; i < _nVertexCount; ++i )
{
for ( int j = 0; j < _nVertexCount; ++j )
{
if ( i != j ) //The node is not itself
{
std::cout << i+1 << " -> " << j+1 << "tt";
if ( INFINITE == _arrDis[i][j] ) //I -> There is no path for j
{
std::cout << "INFINITE" << "tt";
}
else
{
std::cout << _arrDis[i][j] << "tt";
//Since we query the shortest path is inserted from the back forward, so we query the resulting node
//Push the stack and the output pops up in order.
std::stack<int> stackVertices;
int k = j;
do
{
k = _arrPath[i][k];
stackVertices.push( k );
} while ( k != i );
//////////////////////////////////////////////////////////////////////////
std::cout << stackVertices.top()+1;
stackVertices.pop();
unsigned int nLength = stackVertices.size();
for ( unsigned int nIndex = 0; nIndex < nLength; ++nIndex )
{
std::cout << " -> " << stackVertices.top()+1;
stackVertices.pop();
}
std::cout << " -> " << j+1 << std::endl;
}
}
}
}
}
Well, it's time to test it out. Here's what we did:
< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201401/2014122154141737.png" >
The test code is as follows:
int main( void )
{
Graph myGraph;
readGraphData( &myGraph );
//////////////////////////////////////////////////////////////////////////
int arrDis[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];
int arrPath[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];
//First, initialize arrDis
for ( int i = 0; i < myGraph.nVertexCount; ++i )
{
for ( int j = 0; j < myGraph.nVertexCount; ++j )
{
arrDis[i][j] = myGraph.arrArcs[i][j];
}
}
floyd( arrDis, arrPath, myGraph.nVertexCount );
//////////////////////////////////////////////////////////////////////////
printResult( arrDis, arrPath, myGraph.nVertexCount );
//////////////////////////////////////////////////////////////////////////
system( "pause" );
return 0;
}
As shown in figure:
< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201401/2014122154248142.png" >