floyd algorithm study notes

Algorithm idea

Path matrix

Find the shortest path matrix between each two points of a graph through its weight matrix. Starting from the weighted adjacency matrix A=[a(i,j)] n×n of the graph, recursively perform n updates, that is, from the matrix D(0)=A, according to a formula, the matrix D(1) is constructed ; Then use the same formula to construct D(2) from D(1), and so on. Finally, the same formula is used to construct the matrix D(n) from D(n-1). The elements in row i and column j of matrix D(n) are the shortest path length from vertex i to vertex j. D(n) is called the distance matrix of the graph. At the same time, a successor node matrix path can also be introduced to record the distance between two points. the shortest path.

State transition equation

The state transition equation is as follows: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}; map[i,j] ] represents the shortest distance from i to j, K is the breakpoint of exhaustive i, j, and the initial value of map[n,n] should be 0.

Of course, if this road is not accessible, special processing must be done, for example, there is no map[i,k] road.

Core algorithm

1, start from any unilateral path. The distance between all two points is the weight of the edge. If there is no edge connecting the two points, the weight is infinite.

2. For each pair of vertices u and v, see if there is a vertex w such that the path from u to w to v is shorter than the known path. If so update it.

Represent the graph as an adjacency matrix G. If there is a path from Vi to Vj, then G[i,j]=d, and d represents the length of the path; otherwise G[i,j]=infinity. Define a matrix D to record the information of the inserted point. D[i,j] represents the point that needs to be passed from Vi to Vj. Initialize D[i,j]=j. Insert each vertex into the graph and compare the distance after the insertion with the original distance, G[i,j] = min(G[i,j], G[i,k]+G[k,j]), if The value of G[i,j] becomes smaller, then D[i,j]=k. G contains the information of the shortest road between two points, while D contains the information of the shortest path.

Time complexity and space complexity

Time complexity: Because the core algorithm is three for loops using relaxation method, the time complexity is O(n^3)

Space complexity: The entire The algorithm space consumption is an n*n matrix, so its space complexity is O(n^2)

C++ code

// floyd.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include"iostream"
#include"fstream"
#define maxlen 20
#define maximum 100
using namespace std;

typedef struct graph
{
 int vertex;
 int edge;
 int matrix[maxlen][maxlen];
};
int _tmain(int argc, _TCHAR* argv[])
{
 ofstream outwrite;
 outwrite.open("h.txt",ios::app|ios::out);
 outwrite<<"welcome to the graph world!\n";
 outwrite<<"the initial matrix is:\n";
 int vertexnumber;
 int edgenumber;
 int beginning,ending,weight;
 int mindistance[maxlen][maxlen];
 int interval[maxlen][maxlen];
 graph floydgraph;
 cout<<"welcome to the graph world!"<<endl;
 cout<<"input the number of the vertex: ";
 cin>>vertexnumber;
 cout<<"input the number of the edge: ";
 cin>>edgenumber;
 for (int i = 0; i < vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   floydgraph.matrix[i][j]=maximum;
  }
 }
 for (int i = 0; i <edgenumber; i++)
 {
  cout<<"please input the beginning index: ";
  cin>>beginning;
  cout<<"please input the ending index: ";
  cin>>ending;
  cout<<"please input the distance of the two dot: ";
  cin>>weight;
  floydgraph.matrix[beginning][ending]=weight;
 }
 for (int i = 0; i <vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   mindistance[i][j]=floydgraph.matrix[i][j];
   outwrite<<floydgraph.matrix[i][j]<<"\t";
   interval[i][j]=-1;
  }
  outwrite<<"\n";
 }
 for (int k = 0; k <vertexnumber; k++)
 {
  for (int i = 0; i < vertexnumber; i++)
  {
   for (int j = 0; j < vertexnumber; j++)
   {
    if(mindistance[i][j]>mindistance[i][k]+mindistance[k][j])
    {
     mindistance[i][j]=mindistance[i][k]+mindistance[k][j];
     interval[i][j]=k;
    }
   }
  }
 }
 outwrite<<"\n"<<"after the floyd transition, the matrix is: "<<"\n";
 for (int i = 0; i < vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   cout<<"the mindistance between "<<i<<"  and  "<<j <<" is: ";
   cout<<mindistance[i][j]<<endl;
   cout<<"the two points pass through the point: "<<interval[i][j];
   cout<<endl;
   outwrite<<mindistance[i][j]<<"\t";
  }
  outwrite<<"\n";
 }
 outwrite<<"\n";
 outwrite<<"the points between the beginning point and the ending point is:"<<"\n";
 for (int i = 0; i < vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   outwrite<<interval[i][j]<<"\t";
  }
  outwrite<<"\n";
 }
 outwrite.close();
 getchar();
 getchar();
 getchar();
 return 0;
}