Floyd warshall

Floyd warshall가 고안한 알고리즘으로
다대다 최단 거리를 구하는 알고리즘이다.
시간복잡도는 O(n^3)이지만 단순 for문 3중첩이기에
생각보다 빠르게 수행된다.
via라는 2차원 배열을 통하여
최단거리의 경로를 추적할 수 있다.
(reconstruct)함수
[-] Collapse

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

const int MAX_V = 100;
const int INF = (1 << 30);

int V; //정점의 수

int adj[MAX_V][MAX_V]; //인접행렬 연결하는 간선이 없다면 INF
int via[MAX_V][MAX_V]; //via[u][v] u에서 v까지 가는 최단 경로가 경우하는 점 중
                       //가장 번호가 큰 정점 -1로 초기화

void floyd(){
    for (int i = 0; i < V; i++) adj[i][i] = 0; //자기 자신은 거리가 0
    memset(via, -1, sizeof(via)); //-1로 초기화
    for (int k = 0; k < V; k++){//정점 k를 이용하여 갈 수 있는 최단 거리 조사
        for (int i = 0; i < V; i++){
            for (int j = 0; j < V; j++){
                if (adj[i][j] > adj[i][k] + adj[k][i]){//만약 정점 k를 경유 하여
                                                       //짧은 거리에 i에서 j까지 도달할 수 있다면
                    via[i][j] = k;
                    adj[i][j] = adj[i][k] + adj[k][j];
                }
            }
        }
    }
}
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);
    }
}