최단경로 알고리즘

노드와 노드를 이어주는 간선의 어떤 값을 부여한 것을 간선의 가중치(weight)라고 한다.

최단경로 문제는 어떤 노드부터 노드까지 가는 경로의 가중치의 최솟값을 구하는 문제이다.

위의 경로대로 A부터 B까지 가면 1+1+1+2+9 = 14 가 경로의 가중치를 모두 합한 값이다.

하지만 이것은 최단경로가 아니므로 그래프에서 최단경로를 구해보면 12로 다음와 같다.

기초 최단경로 알고리즘은 세가지가 있는데, 특징은 위와 같다.

플로이드 알고리즘은 모든 정점에서 모든 정점까지 최단거리를 구하지만, 그만큼 시간이 많이걸린다.

다익스트라와 벨만포드 알고리즘의 차이점은 가중치의 음수값이 있느냐 없느냐에 따라 나뉜다.

최단경로 문제를 풀 때 중요한 특징은 2가지가 있는데

첫번 째는 X까지 최단거리로 가기 위해서는 그 직전의 노드까지도 최단거리라는 것이다.

만약에  1 --> 6 --> 2 --> 3 --> 8 --> 7 이 최단경로라면

1 --> 6 --> 2 --> 3 --> 8 까지의 경로도 최단경로로 도달 했어야 된다는 뜻이다.

두번 째 특징은 목표지점 X까지 가기 위해서는 X의 인접노드 3개인

Y1 --> X, Y2 --> X, Y3 -->X 로 가는 방법이 있는데,

3가지 경로 중에 가장 작은 가중치 값을 더한 값이 최단경로라는 것이다.

왜냐하면 각각의 Y1, Y2, Y3 까지 최단경로로 왔기 때문에, 마지막에 목표지점 X까지 최단경로를

구하기 위해서는 각각 3개의 노드에서 X까지 간선을 이어주는 가중치 값이 최솟값이여야 한다.

출처 : Algorithm LABS