[알고리즘] 최단 경로 문제

최단 경로 문제가 나오면 다음의 세 가지 알고리즘을 고려해 볼 수 있다. 

 

1. 다익스트라

현재 노드에서 최선의 경로를 하나씩 다 찾으면서도 미리 계산해둔 경로를 활용하기!

 

 준비물

- 시작 노드와 각 노드 사이의 가중치를 나타낸 리스트

 

- visitded 배열

 

 

동작 순서

1. 특정 노드 선택 (1번)

2. 해당 노드와 연결된 노드들로의 엣지 확인 (2,4,5번)

3. 가장 가까운 노드로 이동 ( 2번 ) / 1번은 visited 처리

4. 다시 가장 가까운 노드로 이동 (3번 )->

    이때 맨 처음 출발 노드의 행에도 3번까지의 거리 넣어주기 (2번까지의 거리 + 2->3 거리)

    만약 1번에서 3번까지의 거리가 더 짧으면 이 거리를 유지해야함. 즉

if (2번 노드까지의 거리 + 2번에서 3번 노드까지의 거리) > 1번에서 3번노드까지의 거리 :
	1번에서 3번 노드까지의 거리를 2번 노드까지의 거리 + 2번에서 3번 노드까지의 거리로 갱신.
else :
	pass

 

우선순위 큐를 사용하면시각복잡도가 줄어든다!!! 

 

2. 벨만 포드

다익스트라는 음의 가중치 문제를 해결 못하기에 이를 보완하기 위해 나온 알고리즘

 

음의 가중치나 사이클이 있을 때 사용한다. 

시간 복잡도는 다익스트라보다 크다 ㅠ

다른 점은 벨만 포드는 모든 노드가 시작점이 되어본다. (n번 시행)

기본적인 구현 방식은 똑같다. 

 

 

3. 플로이드 워셜

모든 노드간의 최단 거리를 구할 때 사용. 

위의 두 알고리즘과의 차이점이다. 

 

준비물 

- 노드들을 나타낸 테이블

 

 

각 행은 노드 순서대로. 자기 자신은 0번 처리

길이 없으면 inf 처리

나머지 칸은 가중치 처리

 

구현 방법

위의 점화식을 활용해 특정 노드 k를 거쳐 가는 경우를 확인한다. 

i에서 j까지 가는 경로와 i에서 k를 거쳤다가 k에서 j까지 가는 경로 중 짧은 걸 선택한다는 의미이다.

 

for k in range(1, V+1): #v는 노드 개수
    graph[k][k] = 0 # 사이클 없으므로 자기 자신 0
    for i in range(1, V+1): 
        for j in range(1, V+1): 
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

 

구현 코드를 그냥 외워두는 것이 빠르다 ㅠ