다익스트라 최단 경로 알고리즘 개념 . 1

다익스트라 최단 경로 알고리즘은 현실 세계의 길찾기 문제에서 사용될 수 있는 알고리즘이다.
네덜란드의 컴퓨터 과학자 '에츠허르 다익스트라'가 고안한 알고리즘

길찾기 문제 자체는 다이나믹 프로그래밍의 원리가 적용된 문제라고 할 수 있다.

다익스트라 최단 경로 알고리즘은 길찾기 문제 중에서도 탐욕적인 원리를 이용한다는 점에서
그리디 알고리즘으로 분류한다

 

 

 

최단 거리 테이블을 초기화할 때 다른 모든 노드까지 가는 비용은 무한으로 설정하고
자기자신에 대한 노드는 0으로 설정한다  자기자신에서 자기자신으로 가는 비용은 0이라고 볼 수 있기 때문이다

 

 

 

 

 

다음 단계로 넘어갈 때 아직 방문하지 않은 노드 중에서 최단 거리 비용이 가장 작은 노드를 선택해야 한다

이때 2번 노드와 5번 노드가 모두 같은 비용을 가지고 있는데 이럴 때는 어떤 노드부터 해도 상관 없지만
일반적으로는 더 번호가 낮은 노드부터 선택해서 처리한다

 

 

 

1번 노드에서 2번 노드를 방문했을 경우에는 현재 값보다 2를 거쳐갔을 때 값이 더 크므로(거리가 더 머니까) 갱신하지 않는다

 

 

 

다익스트라 알고리즘에서 마지막 노드는 처리하지 않아도 된다
다른 노드까지의 최단 거리 값이 더이상 바뀌지 않기 때문이다

 

 

 

최단거리가 아닌 최단 경로를 구하려면 추가적인 기능이 더 필요하다

 

 

 

 

 

 

# 파이썬 2차원 리스트 만들기
graph = [[] for i in range(5)]
print(graph)

#출력 결과 :  [[], [], [], [], []]

 

for문에서 i 가 필요 없을 때
for _ in range(m):

 

2차원 리스트에 요소 추가하기
graph[a].append((b,c))

 

최대, 최소 찾는 법
최댓값 변수를 엄청 작은 수,  최솟값 변수를 엄청 큰 수로 초기화한 다음 최댓값, 최솟값 찾기

 

 

 

C++ 코드

 

 

 

자바 코드

 

 

 

자바에서 2차원 리스트 선언
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();

 

 

 

자바에서 2차원 리스트 초기화
graph.add(new ArrayList<Node>());

 

자바에서 ArrayList 를 중첩해 사용하는 경우에는 그래프를 초기화하는 과정에서 
연결된 인접 노드 정보를 담기 위해서 매번 ArrayList 인스턴스를 이용해서
N+1 개만큼 초기화해서 사용해줘야 한다

(N+1 개인 이유는 노드가 0부터가 아닌 1부터 시작하는 걸로 설정했기 때문)

 

자바에서 2차원 리스트 데이터 입력
graph.get(a).add(new Node(b, c));