최단 경로와 최소신장트리의 차이점.
- 무방향 뿐 아니라 방향 그래프에서도 정의
- 그래프에 음의 무게를 가진 싸이클 이 있거나, 무방향 그래프에 음의 무게를 가진 간선 이 있으면 부정.
- 최단 경로 트리는 루트트리
최단 경로 알고리즘
- 음의 무게를 가진 간선이 없는 그래프
- Dijkstra , O(mlog(n)) || O(n^2)
- 음의 무게를 가진 간선이 있는 방향 그래프
- Bellman-Ford , O(mn)
- 비가중 그래프
- BFS , O(n+m)
- DAG
- Topological Ordering , O(n+m)
Dijkstra 알고리즘
- Prims 알고르즘과 비슷
- 정점s로부터 모든 정점들의 최소 거리,
- 전제 : 연결, 무방향 , 음수가 아님
for each v in G.vertices
d(v) = infinity
d(startVertex) = 0
Q <= a priority queue containing all the verties of G using d lables
while(!Q.isEmpty())
u = Q.removeMin
for each e in G.incidentEdges(u)
z = G.oppoiste(u,e)
if(z == Q.elements)
if(d(u) + w(u,z) < d(z))
d(z) = d(u) + w(u,z)
Q.replaceKey(z,d(z))분석
- 그래프 작업 : incidentEdges는 각 정점에 대해 한번씩 호출된다.
- 라벨 작업 : 정점 z의 거리와 위치자 레벨을 O(deg(z))번 읽고 쓴다.
Dijkstra 알고리즘 힙에 기초한 우선순위 큐 분석
- 각 정점은 우선순위 큐에 한번 삽입, 삭제 되고, 각각의 삽입과 삭제는 O(log(n)) , 이를 n번
- 우선순위 큐 내의 정점 z의 키는 최대 deg(z)번 갱신되며, 각각의 키 갱신에 O(log(n))
따라서 인접리스트 구조 로 표현된 경우 O(mlog(n))
최악의 경우 O(n^2 log(n))
Dijkstra 알고리즘, 무순리스트 기초한 우선순위 큐 분석
- 각 정점은 우선순위 큐에 한번 삽입, 삭제 되고, 각각의 삽입O(1) 과 삭제 O(n), 이를 n 번
- 우선순위 큐 내의 정점 z의 키는 최대 deg(z)번 갱신되며, 각각의 키 갱신에 O(1)
따라서 인접리스트 구조 로 표현된 경우 _O(n*n)
무순리스트와, 힙의 비교
- 힙: O(log(m * log(n)))
- 무순리스트 : O(n*n)
즉 최악의 경우만을 생각해서 고려해보면
- 희소그래프 ( m < n*2 / log(n)) 에 대해서는 힙 구현이 유리
- 밀집리스트 ( m > n*2 / log(n)) 에 대해서는 리스트가 유리
Bellman-Ford 알고리즘
- 음의 무게를 가진 간선 있어도 가능
- 방향 간선으로 전제 (그렇지 않으면 음의 무게를 가진 싸이클이 되기 때문)
- 총 n-1회 반복 (연결의 최악의 경우는 일자로 연결될 때이고, 정점(n)일때 간선은 n-1이기 때문)
- n 이상 반복 했을때 정점의 무게가 줄어들면 , 음의 무게를 갖는 사이클이 존재.
- i번째 반복 라운드에서 i개의 간선을 사용하는 최단경로를 찾는다.
- 실행시간 : O(n*m)
- 인접정보를 사용하지 않아서 인접리스트 필요 없
for each v in G.vertices
d(v) = infinity
d(s) = 0
for( i = 1 < i <= n-1)
for each e in G.edges
u = e.start
v = e.end
d(z) = min (d(z), d(u) + w(u,z))
DAG에서의 최단경로
- 다익스트라 알고리즘과의 차이
: 정점을 뽑아내는 순서가 다르다, DAG는 위상순서로 뽑아서 실행 시간이 O(n+m) 이지만, 다익스트라 는 우선순위 큐의 변동때문에 O(m * log(n)) 이다. - 음의 무게를 가진 간선이 있더라도, 작용
- 별다른 데이터구조 사용하지 않음
Compute a toplological ordering of G
for each v in G.vertex
d(v) = infinity
d(startVertex) = 0
for(int i = 0 ; i < n ; i++)
for each e in G.v[i].incidentEdges
z = G.oppoiste(v[i], e)
d(z) = min (d(z), d(v[i], w(v[i], z))모든 쌍 최단경로
- 그래프의 음의 간선을 갖은 간선이 없다면 O(n m log(n)) -> Dijkstra
- 그래프의 음의 간선을 갖은 간선이 있다면 O(n n m) -> bellman-ford
- 동적프로그래밍을 사용하면 o(nnn) 시간으로 수행 가능
for(int i = 0 ; i < n-1; i++)
for(int j = 1 ; j < n ; j++)
if(i==j)
D[i,j] = 0
else if((v1,v2) in G.edge)
D[i,j] = w(v1,v2)
else if(not (v1,v2) in G.edge))
D[i,j] = infinity
for(int k = 0 ; k < n ; k++)
for(int i = 0 ; i< n ;i++)
for(int j = 0; j<n ;j++)
D[i,j] = min(D[i,j] , D[i,k] + D[k,j])