글 읽기 - 플로이드 워셜 알고리즘 질문입니다.

his130 6년 전 0

플로이드 워셜 알고리즘 공부중에

이제 실제 경로를 계산하려고 하는데요..

via 는 플로이드 워셜에서 경로가 갱신될때 값으로 했습니다.

....

if(D[i][j]>D[i][k] + D[k][j])

{

via[i][j]=k;

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

}

....

근데 아래 코드에서 (아래 코드는 종만북 2권 958p 에서 공부한 코드입니다.)

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

이 부분이 왜 필요한지 모르겠습니다.. 좀만 알려주세요..

u랑 v가 다른 상황이 있나요??

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();
        reconstruct(w,v,path);
    }
}

his130 6년 전 0

아.. 아무것도 거치지 않고 연결되어 있는 경우를 추가하는 거네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

플로이드 워셜 알고리즘 질문입니다.

his130 6년 전 0

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말