Floyd-Warshall algorithm

#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);
    }
}

 

 

 

 

 

Floyd-Warshall

모든 쌍 최단거리 알고리즘

 

 

 

 

점화식

0~k까지 정점의 집합에서 u->v의 최단경로

 

 

 

 

 

시간복잡도

O(|V^3|)

 

 

 

 

프로그래밍 대회에서 배우는 알고리즘 문제해결전략2