목록floyd-warshall (1)

매일 조금씩

백준 11403번 : 경로 찾기 [C++]

Floyd Warshall 알고리즘으로 푸는 문제였다. Floyd Warshall 알고리즘은 두 정점간의 거리의 최단거리를 구하는 알고리즘이다. 거쳐가는 정점을 기준으로 두 정점이 각각 연결되어있다면 두정점은 연결된 상태라고 보는 것이 바탕이다. i - k - j 일때, k를 기준으로 for문을 돌리면서 i - k - j 거리를 i - j 거리로 정의하는데 "min( i - j 거리 , i - k - j 거리 )" 를 반복한다. #include #include //#include //memset #include using namespace std; const int MAX = 100; typedef struct { int y, x; }dir; int N; int graph[MAX][MAX]; void f..
알고리즘/최단 경로 2020. 8. 9. 17:58
이전 Prev 1 Next 다음