정점의 개수 V, 간선의 개수 E, 목적지 후보의 개수 W
출발지 s, 정점 g와 h 사이를 지나감
목적지 후보 stack[]
1. 양방향 노선인 간선의 정보 저장
2. 다익스트라 알고리즘을 이용하여 시작점이 s,g,t인 distance를 각각 distart, dig, dih에 저장
**함수에서 리스트 자체를 리턴하여 저장 할 수 있다!!
**리스트를 리턴하지 않고 값을 하나하나 리턴한다면 수많은 다익스트라를 수행 해야 해서 시간초과에 걸릴 수 밖에 없음
3. 목적지 후보까지의 최단 경로는 s->g->h->목적지 후보, s->h->g->목적지 후보 두 가지이므로 목적지와 경로가 같다면 result에 저장
4. 오름차순 정렬하여 출력
'알고리즘 문제 > 다익스트라 최단경로' 카테고리의 다른 글
[Java] 벨만-포드 (타임머신) (0) | 2023.01.19 |
---|---|
다익스트라 최단 경로 (특정 정점을 지나는 최단 경로) (0) | 2022.01.19 |
다익스트라 최단 경로 (최단경로) (0) | 2022.01.19 |