최단 경로
-
두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 것
(간선의 가중치가 없는 경로에서의 최단경로는 걸치고 걸치는 것이 최소인 것) -
하나의 시작 정점에서 끝 정점까지의 최단 경로
* 다익스트라 알고리즘 : 음의 가중치 허용 x- 벨만-포드 알고리즘 : 음의 가중치 허용 o
-
모든 정점들에 대한 최단 경로
* 플로이드-워샬 알고리즘 (DP)
-
MST의 프림 알고리즘과 유사
-
시작정점에서 거리가 최소인 정점을 선택해 나가서 정점 중심으로 해결해 나가는 알고리즘이다.
-> 인접행렬, 인접리스트로 구현된 것이 편리 -
Dijkstras(s, A, D) -> s:시작 정점 , A 배열: 인접 행렬, D 배열: 시작정점에서의 거리
-
D는 시작정점에서 자신으로 오는 최소 비용
-
프림에서의 minEdge : 신장트리에 포함된 정점에서 자신으로 연결하는 간선의 최소비용 ( 간선 중에 최소비용 )
-
다익스트라 D-> 배열 0,1,2,3,4,5가 있으면 0은 0~0, 1은 0~1, 2는 0~2, 3은 0~3, 0~4, 0~5로 거쳐오는 비용 중에 가장 최소인 것을 고르는 것
-
복습
-
MST - 크루스칼: 간선 - 간선들 마다 가중치 존재(전체 간선 중에 제일 비용이 적게 나가는 것부터 시작해서 모든 선들을 연결해놓는 것)
- 프림 : 정점 - 정점을 정해놓고 시작해서 정점과 연결된 다른 정점 중에서 가장 최소의 비용을 갖는 것을 택하고 택하면서 해나가는 것
-
다익스트라
-> 음의 가중치x
-> 시작 정점에서 부터 출발해서 또 다른 정점까지 가장 가깝게(짧게)가는 경로들을 계산(누적하고 그 값이 짧아질 때만 업데이트함)하는 것(어떤경로냐를 찾는 것, 최단 경로를 구하는 것 )(최소 비용)
(다이렉트 or 누군가를 거쳐서 가는 경로)
-> 경유지 개념 (해당 정점까지 다이렉트로 가거나 누구를 경유해서 가거나해서 경유지를 추가를 하면서 그게 더 짧은가?하면서 비교해가는 과정)
D[v] <- A[s][v] : v라는게 모든 정점이 들어가있는 것
U -> 선택된 정점 집합
while U != V
D[w]가 최소인 정점 w 포함 V-U를 선택 -
맨 처음에는 시작점과 경유지가 같게 된다. 그러면 0이 된다.
제일 작은 값인 1부터 시작해서 아직 방문하지 않은 정점들 중에서 D 배열에서 가장 작은 값을 찾아간다.
