맞는데 왜 틀릴까..?

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

다익스트라 최단 경로 (미확인 도착지)

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

정점의 개수 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. 오름차순 정렬하여 출력