[Algorithm - Concept] 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

[Algorithm - Concept] 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

---

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

 

컴퓨터 과학에서, 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R의 추이적 폐포를 찾거나, 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 (슐츠 선거 제도와 결합해서) 찾는 것이 가능하다.

 

In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation R, or (in connection with the Schulze voting system) widest paths between all pairs of vertices in a weighted graph.

 

💊 알고리즘 복잡도 (Algorithm Complcomplexity)

⏰ 시간 복잡도 (Time Complcomplexity)	O(V^3)
📦 공간 복잡도 (Space Complcomplexity)	O(V^2)

---

📄 [Algorithm] Trie Floyd-Warshall Algorithm C++ Source Code

#define VECTOR vector<int>

// 그래프의 인접 행렬 (adj[u][v] = u에서 v로가는 간선의 가중치 값이며 간선이 없을 경우 무한 값을 넣는다.)
vector<VECTOR> adj;

// Graph에서의 모든 정점 사이의 최단 거리를 구하는 알고리즘 (시간복잡도 V^3, 공간복잡도 V^2)
void floyd(const int v) {

	for (int ii = 0; ii < v; ii++) { adj[ii][ii] = 0; }

	for (int kk = 0; kk < v; kk++) { // kk = 경유 노드
		for (int ii = 0; ii < v; ii++) { // ii = 출발 노드
			for (int jj = 0; jj < v; jj++) { // jj 도착 노드
				// adj[ii][kk] (출발점에서 경유점)까지 갈 수 없거나 adj[kk][jj] (경유점에서 도착점)까지 갈 수 없는 경우는 버린다.
				if (adj[ii][kk] == INT_MAX || adj[kk][jj] == INT_MAX) { continue; }

				// adj[ii][jj] (출발점에서 도착점)까지의 거리 중 adj[ii][kk] (출발점에서 경유점) + adj[kk][jj] (경유점에서 도착점)까지의 거리의 값이 더 작은 경우 [ii][jj] 값을 갱신한다.
				adj[ii][jj] = min(adj[ii][jj], adj[ii][kk] + adj[kk][jj]);
			}
		}
	} 

}

---

📄 [Algorithm] Trie Floyd-Warshall Algorithm Pseudo Code

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u,v)
    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
for each vertex v
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
       for j from 1 to |V|
          if dist[i][j] > dist[i][k] + dist[k][j] 
             dist[i][j] ← dist[i][k] + dist[k][j]
             end if

---

🚀 REFERENCE

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전