다익스트라,벨만포드,플로이드 워샬

다익스트라

 

한 정점에서 다른 정점까지 최소로 가는 경로를 구하는 최단 경로 알고리즘

시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식.

시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재한다. 이때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로로 구성된다.

음의 가중치가 있을 경우 사용하지 못한다.

시간복잡도는 일반적으로 O(V^2), 우선순위큐를 사용한다면 O(ElogV)이다.

 

동작과정

1. 시작 정점을 입력 받는다.

2. 거리를 저장할 D배열을 무한대로 초기화 한 후 시작점에서 갈 수 있는 곳의 값은 바꾼다.

3. 아직 방문하지 않은 점들이 가지고 있는 거리 값과 현재 정점에서 방문하지 않은 정점까지의 가중치 합이 작다면 변경한다.

4. 모든 정점을 방문할 때까지 반복한다.

 

 

수도코드

func dijkstra
	for i in D.length
		D[i] = INF
		P[i] = -1
    D[s] = 0
        
    for i in 0->V-1
    	w = INF
        u = -1
        for j in 1->V
			if(!check[j] && D[j]<w
				w = D[j]
				u = j
                
       	for j in adj[u]
			if(D[i] > D[u]+w(u,j))
				D[j] = D[u]+w(u,j)
				P[j] = u;

 

참고 문제

http://boj.kr/1753

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1360&sca=99&sfl=wr_hit&stx=2097

 

 

 

벨만포드

 

한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘.

음의 가중치를 포함하는 그래프에서 최단 경로를 구할 수 있다.

단, 가중치의 합이 음인 사이클은 허용하지 않는다.

다익스트라에 비해 시간이 많이 소요된다.

시간복잡도는 O(VE)

 

동작과정

1. 시작 정점 입력 및 초기화

2. 최단 경로는 순환을 포함해서는 안되므로 V-1번 반복

- 각 정점에 대해 연결된 모든 간선 확인

3. 과정이 끝난 후 다시한번 모든 간선에 대해 확인

- 값이 갱신된다면 음의 사이클이 존재

- 값이 갱신되지 않으면 음의 사이클이 존재하지 않는다.

 

수도코드

func bellmanford
	for i in D
		D[i] = INF
		P[i] = -1
	D[s] = 0
        
	for i in V-1
		for all edge 
			if(D[v] > D[u] + w(u,v)
				D[v] = D[u]+w(u,v)
				P[v] = u
       	
	for all edge
		if D[v] > D[u]+w(u,v)
			return false
	return true

 

참고 문제

 

http://boj.kr/11657

 

 

 

플로이드 워샬

 

모든 쌍에 대해 최단 경로를 구하는 알고리즘이다. 

점 i에서 점 k를 경유하여 j로 가는 경로의 거리와 i에서 j로 가는 경로 중 짧은 것을 선택하는 알고리즘.

음의 간선에서도 찾을 수 있지만 음의 사이클이 없는 경우에만 사용이 가능하다.

O(n^3)의 시간이 걸린다.

 

 

수도코드

 

func FloydWarshall
for k in 1->n
	for i in 1->n		//(i!=k)
    		for j in 1->n	//(j!=k,j!=i)
        		D[i][j] <- min(D[i][k] + D[k][j], D[i][j])

 

참고 문제

http://boj.kr/11404