최단 경로(Shortest Path)

• 가장 짧은 경로를 찾는 알고리즘
• 다양한 알고리즘 유형이 존재하며 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다
  1. Dijkstra
  2. Floyd-Warshall Algorithm

자료구조

• 그래프 자료구조를 이용
  • 참고 : https://velog.io/@sung-ik-je/Graph
• 그래프는 노드와 간선으로 표현

다익스트라(Dijkstra) 알고리즘

알고리즘 백준 1967 참고

한 지점에서 다른 특정 노드까지의 최단 경로

• 가장 짧은 경로를 찾는 알고리즘
  • GPS 소프트웨어의 기본 알고리즘
    
    
• Greed 알고리즘으로 분류
  • 매번 가장 비용이 적은 노드를 선택
    
    
• 인접 리스트 자료구조 이용

기본

• 출발 노드를 시작으로 현재 값 + 간선 값을 최소값으로 갱신하며 마지막-1 노드까지 진행
  • 방문하지 않은 노드들을 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속해서 갱신
  • 마지막 노드의 경우 다른 노드로 가는 경우를 확인할 필요가 없다
    
    
• 간선이 담겨져 있는 배열, 방문 유무를 판단하는 배열, 최단거리 저장하는 배열 3가지 이용
  
  
• 간단한 다익스트라 알고리즘의 경우 시간복잡도 O(V2)
  • V는 노드의 갯수
    
    
• 참고
  • 그래프 이용해 문제 풀 때 index 헷갈리는 것 방지하기 위해 노드의 개수를 +1의 크기로 할당해 노드 번호와 index 일치시킨다
  • 노드의 개수(5000개 이하, 10000개 이상 등)의 따라 코드 다를 수 있다
  • https://velog.io/@sung-ik-je/%ED%9E%99-Heap
  • 최대 시간 복잡도 : O(ElogE)

개선

• 기본의 경우 알고리즘 진행 순서를 보면

  시작 노드 -> 최단 거리 입력
  	FOR문
    		노드 순회해 방문 X, 최소 거리를 지닌 노드 찾아 -> 최단 거리 입력

  
  
• 개선된 경우 최소 거리를 우선순위 큐를 이용해 찾는다
  
  
• 기본의 경우 최대 시간복잡도는 O(V2)로 노드의 갯수가 늘어날수록 문제 해결의 부담 증가하지만 우선순위 큐를 이용해 문제를 개선하는 경우는 최악의 시낙 복잡도 O(ElogV)를 보장하기에 해결할 수 있다
  • V : 노드 갯수, E : 간선 갯수
  • 우선순위 큐 참고 :
    
    
    
    
    
    

플로이드 워셜(Floyd-Warshall Algorithm) 알고리즘

원리

모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담는다
DP 알고리즘의 한 종류, 작은 문제들을 최신화하며 결국 모든 경우의 수를 파악한다

• 모든 지점을 도달하기 위해선 모든 지점을 거쳐간다는 경우 고려해야된다
  • MIN(Mab, Mak + Mkb) : a에서 b를 바로 가는 경우와 k를 거쳐가는 경우 중 더 짧은 거리로 최신화
    a -> b와 a -> k + k -> b 두 가지 경우 중 최단 거리로 최신화

    해당 공식은 노드를 잇고 있는 모든 간선의 조합을 계산한다는 의미
    ex) 1번 노드를 경유한다고 가정했을 때 2 -> 1 -> 3과 같은 경우를 고려한 후 2번 노드를 경유하는 차례에서 4 -> 2 -> 1과 같은 경우가 나오면 결국 4 -> 2-> 1-> 3 경우도 고려하는 것으로 볼 수 있기 때문

결국 N개의 노드를 경유 지점으로 앞, 뒤 모든 경우의 수를 따지기에 N * (N*N), O(N3) 시간 복잡도가 나온다

• N은 노드 갯수라 생각하면된다

자료구조

모든 지점의 최단 거리를 비교하는 것이기에 2차원 배열(인접 행렬 자료구조) 구조를 사용

코드

/*
초기 세팅
	1.초기의 전체 값 무한 변경
	2. i => i, 출발 = 도착인 경우 0으로 초기화
    3. 간선 초기 값 입력 대입
*/

for n		// n개의 노드라 가정
	for start
    	for end
        	Xab = min(Xab, Xstartn + Xnend)