플로이드 알고리즘

모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 알고리즘을 사용하자.

코드 ( C++ )

// 플로이드 알고리즘으로 최단 거리와 최단 경로를 구해 보자.

#include <iostream>

#include <algorithm>

#include <vector>

#include <cstring>

using namespace std;

const int MAX = 100;

// 그래프의 인접 행렬 표현

// adj[u][v] = u 에서 v로 가는 간선의 가중치. 간선이 없으면 아주 큰 값을 넣는다.

int adj[MAX][MAX];

// via[u][v] = u에서 v까지 가는 최단 경로가 경유하는 점 중 가장 번호가 큰 정점

int via[MAX][MAX];

// 정점의 개수

int V;

// 플로이드의 모든 쌍 최단 거리 알고리즘

void floyd()

{

for (int i = 0; i < V; ++i)

adj[i][i] = 0;

memset(via, -1, sizeof(via));

for(int k=0; k<V; ++k)

for(int i=0; i<V; ++i)

for (int j = 0; j < V; ++j)

{

if (adj[i][j] > adj[i][k] + adj[k][j]) {

adj[i][j] = adj[i][k] + adj[k][j];

via[i][j] = k;

}

}

}

void reconstruct(int u, int v, vector<int>& path)

{

if (via[u][v] == -1)

{

path.push_back(u);

if (u != v) path.push_back(v);

}

else

{

int w = via[u][v];

reconstruct(u, w, path);

// w 가 중복으로 들어가므로 지운다.

path.pop_back();

reconstruct(w, v, path);

}

}

int main()

{

cin >> V;

//간선이 없을시 아주 큰 값을 넣어준다.

cout << " flody() 알고리즘 이 전 " << endl;

cout << endl;

for(int i=0; i<V; ++i)

for (int j = 0; j < V; ++j)

{

cin >> adj[i][j];

}

floyd();

cout << endl;

cout << " flody() 알고리즘 이 후 " << endl;

cout << endl;

for (int i = 0; i < V; ++i) {

for (int j = 0; j < V; ++j)

cout << adj[i][j] << " ";

cout << endl;

}

cout << endl;

// 0 에서 1 까지의 최단 경로는 0 - 2 - 3 - 1 이  나와야 한다.

vector<int> path;

cout << "0 에서 1 까지의 최단 경로 " << endl;

reconstruct(0, 1, path);

for (int i = 0; i < path.size(); ++i)

cout << path[i] << " ";

cout << endl; 

return 0;

}

참고 문헌 : 알고리즘 해결 전략