알고리즘 문제/다익스트라 최단경로

다익스트라 최단 경로 (특정 정점을 지나는 최단 경로)

안도일 2022. 1. 19. 18:50

정점의 개수 V, 간선의 개수 E

반드시 거쳐야 하는 정점 n1,n2

1. 양방향이므로 graph[u].append([w,v]), graph[v].append([w,u])

2. 다익스트라 알고리즘 수행

3. n1과 n2를 반드시 거쳐야 하므로 u->n1->n2->v,  u->n2->n1->v 두 가지 경로가 있음

4. 결과에 두 가지 경로중 작은 값을 저장