다익스트라 벨만포드 플로이드

김민지·2022년 12월 17일

코딩테스트

목록 보기

4/31

다익스트라

기본

특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다

방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다(그리디 알고리즘).
해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다(다이나믹 프로그래밍).
dp:점화식같은..

모든 노드를 방문하면 종료 -> 노드개수만큼 반복
1. 최소지점을 선택한다

값이 max_integer가 아니라는것은(distance값이 세팅된 애들중에서) 내가 방문할수있따는 의미니까 그 곳을 방문
방문하지 않았고 거리가 최소인 지점을 찾는다

방문처리
해당지점을 기준으로 그 지점의 인접노드들의 거리값을 갱신한다
그 지점의 인접노드 리스트의 반복문을 돌면서
선택노드의 인접노드 원래비용 vs 선택노드의값 + 현재노드~인접노드 비용
을 비교해서 더 낮은 값으로 갱신한다

다익스트라의 한계

다음과 같이 음수+cycle이 있으면 cycle을 돌면서 계속해서 값이 적어지기때문에 최적의 경로를 찾을 수 없게된다.
그러니까 다익스트라는 음수+cycle 을 미포함한다는 가정하에 할 수 있는 알고리즘이다

다익스트라는 행위하나에 방문처리를 한다. 근데 사이클은 나중에 발견될수도있는데, 그러니까 행위하나로 해당 노드의 최소경로가 한번에 결정되지 않는다는 얘기다.(음수+cycle이존재한다면)
음수+cycle이 존재한다면. 하나의 값으로 최소경로가 존재하지 않게된다

다익스트라 vs 프림알고리즘

최소신장트리: 각 노드들의 가중치가 가장 작은 상태로 모든 노드를 연결하는 경로
다익스트라: 두노드사이의 최단거리를 구해주는 알고리즘

최소신장트리는 두 노드사이가 최단거리가 아닐수도있다
최소스패닝트리가 최단경로트리를 보장해주지 않고, 최단경로트리가 최소스패닝트리를 보장해주지 않는다

벨만포드

한노드 -> 다른노드로 가는 최단경로를 구해줌. 음수 가중치가능
음수+cycle 을 포함하면 벨만포드를 사용해야한다

① 출발 노드 설정
② 최단 거리를 저장할 배열을 초기화
③ 전체 간선을 하나씩 확인
④ 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
⑤ 모든 노드에 연결되어 있는 모든 간선을 확인할 때까지 ③ ~ ④반복수행
⑤-1 이때, 마지막 반복에서 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재
(∵ 음수 간선 순환은 돌면 돌수록 값이 작아지기 때문)

의문

바깥쪽 for문은 왜필요한것일까? 모든 간선에 대해서 돌면 완료되는것같은데.
간선의 입력이 다르게 들어올수있다. 만약에
1->3
2->3
1->3 이렇게 주어졋다고 했을때
시작을 1부터하는데 2->3의 간선부터 들어온다면 우리는 2가 방문되지않은 노드이기때문에 pass할것이다. 그대신 1로부터 시작해서 바로 도착하는노드에 대해서는 최소경로를 보장할것이다.
node가 n개있으면 가장 먼 노드는 최대 n-1개의 간선을 거쳐서 도착할수있기에
(그리고 그 경우가 노드가 일렬로 나열되어있는것을 상상할수있기에.)
n-1번정도는 반복을 해야 정답을 보장할수있는것이다
```
     
```