4. Paths in graphs

4.1. Distances

그래프에서 두 정점간 거리는 정점간 최단 경로의 길이이다.

4.2. Breadth-first search

비가중치 비방향그래프에서 두 정점간 거리는 너비 우선 탐색으로 찾는다.

Correctness and efficiency

너비 우선 탐색으로 찾은 거리는 올바르며 선형 시간에 끝난다.

4.3. Lenghts on edges

간선에 가중치가 있으면 어떻게 할까?

4.4. Dijstra’s algorithm

4.4.1. An adaptation of breadth-first search

간선 길이가 양의 정수라면?

A more convenient graph

간선 길이가 양의 정수면 l – 1개의 중간 노드를 추가해 너비 우선 탐색을 적용할 수 있다.

Alarm clocks

더 좋은 방법은 없나?

Dijkstra’s algorithm

너비 우선 탐색을 변형한 다익스트라의 알고리즘이 있다.

4.4.2. An alternative derivation

다익스트라 알고리즘의 정당성은 여러 방식으로 생각해볼 수 있다.

4.4.3. Running time

우선순위 큐를 어떻게 구현하냐에 따라 다르지만 이진 힙으로 구현할 시 O((V + E)\log V)이다.

4.5. Priority queue implementation

4.5.1. Array

우선순위 큐를 배열로 구현하면 총 O(V^{2})이다.

4.5.2. Binary heap

이진 힙으로 구현하면 O((V + E) \log V)이다.

4.5.3. d-ary heap

d진 힙으로 구현하면 O((Vd + E)\frac{\log V}{\log d})이다.

4.6. Shortest paths in the presence of negative edges

4.6.1. Negative edges

다익스트라의 알고리즘은 음의 간선이 있을 때는 쓸 수 없다. 이 때는 벨만-포드 알고리즘을 쓴다.

4.6.2. Negative cycles

음의 간선이 있으면서 음의 순환이 있으면 벨만-포드도 실패한다. 최단거리 자체가 잘 정의되지 않는다.

4.7. Shortest paths in dags

방향 비순환그래프에서는 탐욕적 알고리즘으로 쉽게 선형 시간에 최단 거리를 구할 수 있다. 최장 거리도 똑같이 구할 수 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중