알고리즘 문제/다익스트라 최단경로
다익스트라 최단 경로 (특정 정점을 지나는 최단 경로)
안도일
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. 결과에 두 가지 경로중 작은 값을 저장