Studiennotizen zum Floyd-Algorithmus

Algorithmusidee

Pfadmatrix

Finden Sie die kürzeste Pfadmatrix zwischen jeweils zwei Punkten eines Diagramms anhand seiner Gewichtsmatrix. Führen Sie ausgehend von der gewichteten Adjazenzmatrix A = [a (i, j)] n × n des Diagramms rekursiv n Aktualisierungen durch, dh ausgehend von der Matrix D (0) = A gemäß einer Formel die Matrix D ( 1) wird konstruiert; Verwenden Sie dann dieselbe Formel, um D(2) aus D(1) zu konstruieren, und so weiter. Schließlich wird dieselbe Formel verwendet, um die Matrix D(n) aus D(n-1) zu konstruieren. Die Elemente in Zeile i und Spalte j der Matrix D(n) sind die kürzeste Pfadlänge vom Scheitelpunkt i zum Scheitelpunkt d(n) und werden gleichzeitig als Abstandsmatrix des Diagramms bezeichnet Außerdem wird der kürzeste Weg eingeführt, um den Abstand zwischen zwei Punkten aufzuzeichnen.

Zustandsübergangsgleichung

Die Zustandsübergangsgleichung lautet wie folgt: map[i,j]:=min{map[i,k] map[k,j],map[i, j] }; Map[i,j] stellt den kürzesten Abstand von i nach j dar, K ist der Haltepunkt von erschöpfendem i,j und der Anfangswert von Map[n,n] sollte 0 sein.

Wenn diese Straße nicht zugänglich ist, muss natürlich eine spezielle Verarbeitung durchgeführt werden, z. B. gibt es keine Karte [i, k] Straße.

Kernalgorithmus

1, ausgehend von einem beliebigen einseitigen Pfad. Der Abstand zwischen allen beiden Punkten ist das Gewicht der Kante. Wenn es keine Kante gibt, die die beiden Punkte verbindet, ist das Gewicht unendlich.

2. Überprüfen Sie für jedes Scheitelpunktpaar u und v, ob es einen Scheitelpunkt w gibt, sodass der Weg von u nach w nach v kürzer ist als der bekannte Weg. Wenn ja, aktualisieren Sie es.

Stellen Sie den Graphen als Adjazenzmatrix G dar. Wenn es eine Straße gibt, die von Vi nach Vj erreichbar ist, dann ist G[i,j]=d, d stellt die Länge der Straße dar, andernfalls G[i,j ]= Unendlich. Definieren Sie eine Matrix D, um die Informationen des eingefügten Punkts D[i,j] aufzuzeichnen, der den Punkt darstellt, der von Vi an Vj übergeben werden muss. Fügen Sie jeden Scheitelpunkt in das Diagramm ein und vergleichen Sie den Abstand nach dem Einfügen mit dem ursprünglichen Abstand, G[i,j] = min( G[i,j], G[i,k] G[k,j] ), wenn G Der Wert von [i,j] wird kleiner, dann ist D[i,j]=k. G enthält die Informationen über die kürzeste Straße zwischen zwei Punkten, während D die Informationen über den kürzesten Weg enthält.

Zeitkomplexität und Raumkomplexität

Zeitkomplexität: Da der Kernalgorithmus aus drei For-Schleifen besteht und die Entspannungsmethode verwendet, beträgt die Zeitkomplexität O (n^3)

Raumkomplexität: Der Raumverbrauch des gesamten Algorithmus ist eine n*n-Matrix, daher beträgt seine Raumkomplexität 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;
}