목록플로이드와샬 (1)

Binary Journey

[Algorithm] Floyd Warshall Algorithm (플로이드 와샬 알고리즘)

지난번 배운 데이크스트라 알고리즘과 비슷하다. 데이크스트라는 한 정점에서 모든 노드로 향하는 가장 최단 거리를 구하는 것이고 플로이드 알고리즘은 모든 노드에서 모든 노드로 가는 최단 거리를 구한다는 점에서 약간의 차이점이 있다. 위 설명이 이해가 가기 어렵겠지만 예를 들어 문래동, 목동, 화곡동, 신대방동 이렇게 네 곳이 있을 때 문래동을 경유하는 최단 거리, 목동을 경유하는 최단거리, 화곡동을 경유하는 최단 거리, 신대방동을 경유하는 최단거리를 구한다고 생각하면 된다. 위 노드에 대해 코드를 작성하자면 ** C++ #include int number = 4; int INF = 1000000000; // 자료 배열 초기화 int a[4][4] = { { 0, 5, INF, 8 }, { 7, 0, 9, I..
Algorithm/알고리즘 스터디(2021.07) 2021. 10. 17. 20:52
이전 Prev 1 Next 다음