Algorithm/그래프
Floyd-Warshall algorithm
jhg0406
2020. 1. 23. 14:41
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <iostream>
using namespace std;
#define MAX_V 1111
//플로이드 알고리즘에서 실제 최단 경로 계산하기
//정점의 개수
int V;
//그래프의 인접 행렬 표현
//adj[u][v] : u에서 v로 가는 간선의 가중치, 간선이 없으면 INF를 넣는다.
int adj[MAX_V][MAX_V];
//via[u][v] : u에서 v까지 가는 최단 경로가 경유하는 점 중 가장 번호가 큰 정점
//-1로 초기화해 둔다
int via[MAX_V][MAX_V];
//플로이드의 모든 쌍 최단 거리 알고리즘
void floyd2()
{
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])
{
via[i][j] = k;
adj[i][j] = adj[i][k] + adj[k][j];
}
}
//u에서 v로 가는 최단 경로를 꼐산해 path에 저장한다
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);
path.pop_back(); //w가 중복으로 들어가므로 지운다
reconstruct(w, v, path);
}
}
|
cs |
Floyd-Warshall
모든 쌍 최단거리 알고리즘
점화식
시간복잡도
O(|V^3|)
프로그래밍 대회에서 배우는 알고리즘 문제해결전략2