플로이드 알고리즘 연구 노트

알고리즘 아이디어

경로 행렬

가중치 행렬을 통해 그래프의 모든 두 점 사이의 최단 경로 행렬을 찾습니다. 그래프의 가중 인접 행렬 A=[a(i,j)]n×n에서 시작하여 n개의 업데이트, 즉 행렬 D(0)=A로부터 다음 공식에 따라 재귀적으로 업데이트를 수행합니다. 행렬 D( 1)이 구성됩니다. 그런 다음 동일한 공식을 사용하여 D(1)에서 D(2)를 구성합니다. 마지막으로 동일한 공식을 사용하여 D(n-1)로부터 행렬 D(n)을 구성합니다. 행렬 D(n)의 i행과 j열의 요소는 정점 i에서 정점 j까지의 최단 경로 길이입니다. 동시에, 후속 노드 행렬 경로는 그래프의 거리 행렬이라고 합니다. 또한 두 지점 사이의 거리를 기록하는 방법도 도입되었습니다.

상태 전이 방정식

상태 전이 방정식은 다음과 같습니다. map[i,j]:=min{map[i,k]+map[k,j],map[i ,j ]}; map[i,j]는 i에서 j까지의 최단 거리를 나타내고, K는 전체 i,j의 중단점이며, map[n,n]의 초기 값은 0이어야 합니다.

물론 이 도로에 접근이 불가능한 경우에는 지도[i,k] 도로가 없는 등 특별한 처리를 해야 합니다.

핵심 알고리즘

1, 모든 단방향 경로에서 시작합니다. 두 점 사이의 거리는 모서리의 가중치입니다. 두 점을 연결하는 모서리가 없으면 가중치는 무한합니다.

2. 각 정점 u와 v에 대해 u에서 w, v까지의 경로가 알려진 경로보다 짧은 정점 w가 있는지 확인합니다. 그렇다면 업데이트하세요.

그래프를 인접 행렬 G로 표현합니다. Vi에서 Vj까지 도달할 수 있는 도로가 있으면 G[i,j]=d, d는 도로의 길이를 나타냅니다. 그렇지 않으면 G[i,j ]= 무한대. 삽입된 점의 정보를 기록하기 위해 행렬 D를 정의합니다. D[i,j]는 Vi에서 Vj로 전달되어야 하는 점을 나타냅니다. D[i,j]=j를 초기화합니다. 각 정점을 그래프에 삽입하고 삽입점 이후의 거리를 원래 거리와 비교합니다. G[i,j] = min(G[i,j], G[i,k]+G[k,j]), G[i,j]의 값이 작아지면 D[i,j]=k가 됩니다. G에는 두 지점 사이의 최단 경로 정보가 포함되고, D에는 최단 경로 정보가 포함됩니다.

시간 복잡도와 공간 복잡도

시간 복잡도: 핵심 알고리즘은 완화법을 사용한 3개의 for 루프이므로 시간 복잡도는 O입니다. (n^3)

공간 복잡도: 전체 알고리즘의 공간 소비는 n*n 행렬이므로 공간 복잡도는 O(n^2)

C++ 코드

// 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;
}