Shortest Paths - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:24:55Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:24 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[알고리즘 설계와 분석#문제\|알고리즘 설계와 분석]]		상위 문서: [[알고리즘 설계와 분석#문제\|알고리즘 설계와 분석]]

Pinkgo: /* Transitive Closure */

2025-11-18T03:14:09Z

Transitive Closure

← 이전 판		2025년 11월 18일 (화) 03:14 판
126번째 줄:		126번째 줄:
	따라서, Floyd 알고리즘을 수행하기 위해서는 아래와 같이 인접 행렬(Adjacency Matrix)로부터 초기 거리 행렬 D를 구성해야 한다:		따라서, Floyd 알고리즘을 수행하기 위해서는 아래와 같이 인접 행렬(Adjacency Matrix)로부터 초기 거리 행렬 D를 구성해야 한다:
	<math>D[i,j]=		<math>D[i,j]=
	\begin{cases}		\begin{cases}
	0 & if\,\,\, i = j \\		0 & if\,\,\, i = j \\
	w(i,j) & if\,\,\, edge(i, j) \in E \\		w(i,j) & if\,\,\, edge(i, j) \in E \\
	\infty, & otherwise		\infty, & otherwise
	\end{cases}		\end{cases}
	</math>		</math>
	위의 식은 간선 (i,i)의 거리 D[i,i]는 0, 간선 (i, j)가 존재하면 거리 D[i,j]는 w(i,j), 간선 (i, j)가 존재하지 않으면 그 거리 D[i,j]는 무한대라는 것을 의미한다. 이때 동적 프로그래밍의 상태 정의는 아래와 같다:		위의 식은 간선 (i,i)의 거리 D[i,i]는 0, 간선 (i, j)가 존재하면 거리 D[i,j]는 w(i,j), 간선 (i, j)가 존재하지 않으면 그 거리 D[i,j]는 무한대라는 것을 의미한다. 이때 동적 프로그래밍의 상태 정의는 아래와 같다:
	* <math>d[i,j]^k</math>: 1~k번 정점만을 중간 노드로 사용할 수 있을 때, i→j의 최단거리		* <math>d[i,j]^k</math>: 1~k번 정점만을 중간 노드로 사용할 수 있을 때, i→j의 최단거리
172번째 줄:		172번째 줄:

	===Transitive Closure===		===Transitive Closure===
			[[파일:Figure 3. Transitive Closure.png\|섬네일\|Figure 3. Transitive Closure]]
	Floyd 알고리즘을 활용하여 가중치가 아니라 연결 여부(True/False) 만 고려하여 Transitive Closure에 활용할 수 있다. 이를 위해 아래와 같은 식을 만들 수 있다:		Floyd 알고리즘을 활용하여 가중치가 아니라 연결 여부(True/False) 만 고려하여 Transitive Closure에 활용할 수 있다. 이를 위해 아래와 같은 식을 만들 수 있다:
	<math>C[i,j]=1\,\,\, if\,\, there\,\, exists\,\, a\,\, path\,\, i \rightarrow j </math>		<math>C[i,j]=1\,\,\, if\,\, there\,\, exists\,\, a\,\, path\,\, i \rightarrow j </math>
	위 식을 이용하여 Floyd 알고리즘의 논리를 그대로 Boolean 연산으로 적용할 수 있다:		위 식을 이용하여 Floyd 알고리즘의 논리를 그대로 Boolean 연산으로 적용할 수 있다:
	<math>C[i,j] = C[i,j] \lor (C[i,k]\land C[k,j])</math>		<math>C[i,j] = C[i,j] \lor (C[i,k]\land C[k,j])</math>
			Figure 3는 이를 쉽게 설명한 예시이다.

	==각주==		==각주==

Pinkgo: /* Dynamic Programming */

2025-11-17T23:55:43Z

Dynamic Programming

← 이전 판		2025년 11월 17일 (월) 23:55 판
127번째 줄:		127번째 줄:
	<math>D[i,j]=		<math>D[i,j]=
	\begin{cases}		\begin{cases}
	0 & if i = j \\		0 & if\,\,\, i = j \\
	w(i,j) & if edge(i, j) \in E \\		w(i,j) & if\,\,\, edge(i, j) \in E \\
	\infty, & otherwise		\infty, & otherwise
	\end{cases}		\end{cases}

Pinkgo: /* How Dijkstra’s Algorithm works */

2025-11-17T21:23:20Z

How Dijkstra’s Algorithm works

← 이전 판		2025년 11월 17일 (월) 21:23 판
30번째 줄:		30번째 줄:
	다익스트라 알고리즘의 시작 단계(Initialization)에서는 출발점 s에서 각 노드까지의 거리를 초기화한다. 이는 아래와 같다:		다익스트라 알고리즘의 시작 단계(Initialization)에서는 출발점 s에서 각 노드까지의 거리를 초기화한다. 이는 아래와 같다:
	# d(s, s) = 0 (자기 자신까지의 거리는 0)		# d(s, s) = 0 (자기 자신까지의 거리는 0)
	# 나머지 노드는 무한대로 설정한<ref>다른 정점에 대한 거리를 모르기 때문이다.</ref> 후, 정점 s에서 연결된 ~~간선 중 가장 짧은 간선을~~ 이용해 인접 노드의 거리값을 갱신한다.		# 나머지 노드는 무한대로 설정한<ref>다른 정점에 대한 거리를 모르기 때문이다.</ref> 후, 정점 s에서 연결된 간선들을 이용해 인접 노드의 거리값을 갱신한다.
	다익스트라 알고리즘은 시작 단계 이후, 주어진 거리 배열(distance array)를 업데이트(update)하며 최단 경로를 탐색한다. 이는 정점 s에서 어떤 정점 x에 대한 최단 경로가 확정되면, 그 노드와 연결된 모든 간선을 검사해 s→x→y 가 기존 s→y보다 짧은지 확인하고 갱신하는 방식이다. 즉, 거리 배열(distance array)을 유지하면서 새 노드를 확정할 때마다 그 이웃 노드들의 거리값을 업데이트하는 방식이다. 아래는 다익스트라 알고리즘에 대한 수도 코드이다:		다익스트라 알고리즘은 시작 단계 이후, 주어진 거리 배열(distance array)를 업데이트(update)하며 최단 경로를 탐색한다. 이는 정점 s에서 어떤 정점 x에 대한 최단 경로가 확정되면, 그 노드와 연결된 모든 간선을 검사해 s→x→y 가 기존 s→y보다 짧은지 확인하고 갱신하는 방식이다. 즉, 거리 배열(distance array)을 유지하면서 새 노드를 확정할 때마다 그 이웃 노드들의 거리값을 업데이트하는 방식이다. 아래는 다익스트라 알고리즘에 대한 수도 코드이다:
	<syntaxhighlight lang="go">		<syntaxhighlight lang="go">

Pinkgo: /* How Dijkstra’s Algorithm works */

2025-11-17T21:17:19Z

How Dijkstra’s Algorithm works

← 이전 판		2025년 11월 17일 (월) 21:17 판
30번째 줄:		30번째 줄:
	다익스트라 알고리즘의 시작 단계(Initialization)에서는 출발점 s에서 각 노드까지의 거리를 초기화한다. 이는 아래와 같다:		다익스트라 알고리즘의 시작 단계(Initialization)에서는 출발점 s에서 각 노드까지의 거리를 초기화한다. 이는 아래와 같다:
	# d(s, s) = 0 (자기 자신까지의 거리는 0)		# d(s, s) = 0 (자기 자신까지의 거리는 0)
	# 나머지 노드는 무한대로 설정한<ref>다른 정점에 대한 거리를 모르기 때문이다.</ref> 후, 각 정점 s에서 연결된 간선 중 가장 짧은 간선을 이용해 인접 노드의 거리값을 갱신한다.		# 나머지 노드는 무한대로 설정한<ref>다른 정점에 대한 거리를 모르기 때문이다.</ref> 후, 정점 s에서 연결된 간선 중 가장 짧은 간선을 이용해 인접 노드의 거리값을 갱신한다.
	다익스트라 알고리즘은 시작 단계 이후, 주어진 거리 배열(distance array)를 업데이트(update)하며 최단 경로를 탐색한다. 이는 정점 s에서 어떤 정점 x에 대한 최단 경로가 확정되면, 그 노드와 연결된 모든 간선을 검사해 s→x→y 가 기존 s→y보다 짧은지 확인하고 갱신하는 방식이다. 즉, 거리 배열(distance array)을 유지하면서 새 노드를 확정할 때마다 그 이웃 노드들의 거리값을 업데이트하는 방식이다. 아래는 다익스트라 알고리즘에 대한 수도 코드이다:		다익스트라 알고리즘은 시작 단계 이후, 주어진 거리 배열(distance array)를 업데이트(update)하며 최단 경로를 탐색한다. 이는 정점 s에서 어떤 정점 x에 대한 최단 경로가 확정되면, 그 노드와 연결된 모든 간선을 검사해 s→x→y 가 기존 s→y보다 짧은지 확인하고 갱신하는 방식이다. 즉, 거리 배열(distance array)을 유지하면서 새 노드를 확정할 때마다 그 이웃 노드들의 거리값을 업데이트하는 방식이다. 아래는 다익스트라 알고리즘에 대한 수도 코드이다:
	<syntaxhighlight lang="go">		<syntaxhighlight lang="go">

Pinkgo: /* Dijkstra’s Algorithm */

2025-11-17T21:14:37Z

Dijkstra’s Algorithm

← 이전 판		2025년 11월 17일 (월) 21:14 판
25번째 줄:		25번째 줄:

	==Dijkstra’s Algorithm==		==Dijkstra’s Algorithm==
	다익스트라 알고리즘(Dijkstra’s Algorithm)은 간선의 가중치가 양수인 가중치 그래프에서의 최단 경로를 탐색하는 알고리즘이다. 다익스트라 알고리즘의 핵심 원리는 부분 최적성(Optimal Substructure)이다. 부분 최적성이란, 만약 경로 s→…→x→…→t 가 최단 경로라면, 그 일부인 s→…→x 도 역시 최단 경로여야 한다는 뜻이다. 이를 이용하여 Dynamic Programming 방식으로 접근할 수 있다. 이는 이미 구한 가까운 노드들의 최단 경로 정보를 이용해 점점 멀리 있는 노드들의 최단 경로를 확장해 나가는 구조이다.		다익스트라 알고리즘(Dijkstra’s Algorithm)은 간선의 가중치가 양수인 가중치 그래프에서의 최단 경로를 탐색하는 알고리즘이다. 다익스트라 알고리즘의 핵심 원리는 부분 최적성(Optimal Substructure)이다. 부분 최적성이란, 만약 경로 s→…→x→…→t 가 최단 경로라면, 그 일부인 s→…→x 도 역시 최단 경로여야 한다는 뜻이다. 이를 이용하여 [[Dynamic Programming]] 방식으로 접근할 수 있다. 이는 이미 구한 가까운 노드들의 최단 경로 정보를 이용해 점점 멀리 있는 노드들의 최단 경로를 확장해 나가는 구조이다.

	===How Dijkstra’s Algorithm works===		===How Dijkstra’s Algorithm works===

Pinkgo: /* Dynamic Programming */

2025-10-31T02:30:41Z

Dynamic Programming

← 이전 판		2025년 10월 31일 (금) 02:30 판
119번째 줄:		119번째 줄:

	===Dynamic Programming===		===Dynamic Programming===
	Floyd 알고리즘은 동적 ~~프로그래밍을~~ 기반으로 한다. 동적 프로그래밍은 아래와 같은 단계를 통해 문제를 해결한다:		Floyd 알고리즘은 [[Dynamic Programming\|동적 프로그래밍]]을 기반으로 한다. 동적 프로그래밍은 아래와 같은 단계를 통해 문제를 해결한다:
	# 최적해의 구조를 파악한다.(Optimal Substructure)		# 최적해의 구조를 파악한다.(Optimal Substructure)
	# 그 값을 재귀적으로 정의한다.(Recurrence)		# 그 값을 재귀적으로 정의한다.(Recurrence)

Pinkgo: /* Implementation of Floyd's Algorithm */

2025-10-25T18:15:01Z

Implementation of Floyd's Algorithm

← 이전 판		2025년 10월 25일 (토) 18:15 판
170번째 줄:		170번째 줄:
	}		}
	</syntaxhighlight>		</syntaxhighlight>

			===Transitive Closure===
			Floyd 알고리즘을 활용하여 가중치가 아니라 연결 여부(True/False) 만 고려하여 Transitive Closure에 활용할 수 있다. 이를 위해 아래와 같은 식을 만들 수 있다:
			<math>C[i,j]=1\,\,\, if\,\, there\,\, exists\,\, a\,\, path\,\, i \rightarrow j </math>
			위 식을 이용하여 Floyd 알고리즘의 논리를 그대로 Boolean 연산으로 적용할 수 있다:
			<math>C[i,j] = C[i,j] \lor (C[i,k]\land C[k,j])</math>

	==각주==		==각주==

Pinkgo: /* Dynamic Programming */

2025-10-25T18:11:20Z

Dynamic Programming

@@ 139번째 줄: / 139번째 줄: @@
   <math>d[i,j]^k=min(d[i,j]^{k-1}, d[i,k]^{k-1}+d[k,j]^{k-1})</math>
 즉, 위 점화식은 “i에서 j로 갈 때 vertex k를 거치는 것이 더 짧은가?”를 확인해서 갱신하는 것이다. k를 거치지 않은 최단거리 vs k를 거치는 경로의 거리 중 더 짧은 걸 선택하고, 이렇게 k=1→n 순서로 모든 정점을 중간노드로 고려하면, 최종적으로 모든 쌍의 최단경로를 완성할 수 있다.
 ==각주==

Pinkgo: /* Floyd’s Algorithm */

2025-10-25T18:06:08Z

Floyd’s Algorithm

← 이전 판		2025년 10월 25일 (토) 18:06 판
116번째 줄:		116번째 줄:

	==Floyd’s Algorithm==		==Floyd’s Algorithm==
			Floyd 알고리즘은 그래프의 모든 정점 쌍 간 최단 경로(All-Pairs Shortest Path) 를 찾는 알고리즘이다. 하나의 정점 s로부터 다른 모든 정점까지의 최단경로는 Dijkstra 알고리즘으로 구할 수 있다. 하지만 모든 정점 쌍 사이의 최단 경로를 찾기 위해서 Dijkstra를 n번 실행하면 대략 O(n<sup>3</sup>)의 시간 복잡도가 소요된다. 따라서 모든 정점 쌍 사이의 최단 경로를 더욱 효율적으로 찾고자 하는 것이 Floyd 알고리즘의 시작점이다.

			===Dynamic Programming===
			Floyd 알고리즘은 동적 프로그래밍을 기반으로 한다. 동적 프로그래밍은 아래와 같은 단계를 통해 문제를 해결한다:
			# 최적해의 구조를 파악한다.(Optimal Substructure)
			# 그 값을 재귀적으로 정의한다.(Recurrence)
			# Bottom-up 방식으로 계산한다.
			# 계산된 값으로부터 최적해를 복원한다.
			따라서, Floyd 알고리즘을 수행하기 위해서는 아래와 같이 인접 행렬(Adjacency Matrix)로부터 초기 거리 행렬 D를 구성해야 한다:
			<math>D[i,j]=
			\begin{cases}
			0 & if i = j \\
			w(i,j) & if edge(i, j) \in E \\
			\infty, & otherwise
			\end{cases}
			</math>
			위의 식은 간선 (i,i)의 거리 D[i,i]는 0, 간선 (i, j)가 존재하면 거리 D[i,j]는 w(i,j), 간선 (i, j)가 존재하지 않으면 그 거리 D[i,j]는 무한대라는 것을 의미한다. 이때 동적 프로그래밍의 상태 정의는 아래와 같다:
			* <math>d[i,j]^k</math>: 1~k번 정점만을 중간 노드로 사용할 수 있을 때, i→j의 최단거리
			* 즉, k가 커질수록 고려할 수 있는 중간노드의 집합이 확장됨.
			* 경로는 vertex k를 “지나거나(through k)” 또는 “지나지 않거나” 두 경우 뿐이다.
			이를 기반으로 아래와 같이 점화식(Recurrence Relation)을 세울 수 있다:
			<math>d[i,j]^k=min(d[i,j]^{k-1}, d[i,k]^{k-1}+d[k,j]^{k-1})</math>
			즉, 위 점화식은 “i에서 j로 갈 때 vertex k를 거치는 것이 더 짧은가?”를 확인해서 갱신하는 것이다. k를 거치지 않은 최단거리 vs k를 거치는 경로의 거리 중 더 짧은 걸 선택하고, 이렇게 k=1→n 순서로 모든 정점을 중간노드로 고려하면, 최종적으로 모든 쌍의 최단경로를 완성할 수 있다.

	==각주==		==각주==