Dijkstra

🔒 문제 🧠 아이디어 반드시 2개의 정점을 경유해서 가야하므로 Way point (경유지) 1, 2 가 존재할 때 선택할 수 있는 경로는 다음 2가지로 좁혀진다. 출발 노드 -> 경유지 1 -> 경유지 2 -> 목적지 출발 노드 -> 경유지 2 -> 경유지 1 -> 목적지 여기서 구해야 할 값은 다음 5가지다. 출발 노드 -> 경유지 1의 최단경로 출발 노드 -> 경유지 2의 최단경로 경유지 1 -> 목적지의 최단경로 경유지 2 -> 목적지의 최단경로 경유지 1 - 경유지2 의 최단경로 양방향 그래프기 때문에 경유지 1-> 경유지 2, 경유지 2-> 경유지1는 서로 거리가 같기 때문에 한 번만 구하면 된다. 최단 경로를 구해야하므로 Dijkstra 알고리즘 사용한다. 출발 노드 -> 경유지 1,2 는 한..

🔒 문제 🧠 아이디어 그래프상 간선과 정점이 주어지고 시작점 - 목적지 - 간선비용을 입력받는 전형적인 최소 비용 경로 문제. 단 경로 과정을 모두 킵해야 하므로 다익스트라 알고리즘 상에서 특정 지점에 도착하기 직전 지점을 배열에 담아 보관하고 시작점에 도달하기 까지 목적지로부터 거꾸로 출력해내기만 하면 되겠다. 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader import java.lang.StringBuilder import java.util.* import kotlin.collections.ArrayList fun dijkstra(startVertexNum: Int, distances: Array, preVert..

When to use? 임의의 한 정점에서 모든 정점으로의 최단 경로 및 비용을 구할 때. 특정 출발 지점에서 도착지점까지의 최단 경로 및 비용을 구할 때 # shortest path # greedy Algorithm 1. Create shortestPath Set, distance array table || (visited array) 2. initialize all vertices with make start node weight '0', reamin node weight 'INF' 3. set || priorityQueue != empty (a) Pick minimum vertex (b) check all adjacent edge weight compare distance [adjacentVerte..