다익스트라3 [LEET CODE] 787. Cheapest Flights Within K Stops ( 다익스트라 알고리즘 ) # Problem There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w. Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1. Constraints: The number of nodes n will be in range [1, 100], with nodes.. 2021. 4. 14. [LEET CODE] 743. Network Delay Time ( 다익스트라 알고리즘) # Problem You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If.. 2021. 4. 14. [코딩 + 알고리즘 완주반] 21일차. 최단 경로 알고리즘 # 최단 경로 문제 두 노드를 잇는 가장 짧은 경로 찾기 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로 # 단일 출발 및 단일 도착 최단 경로 문제 특정 노드에서 특정 노드에 도착하는 가장 짧은 경로 찾기 # 단일 출발 최단 경로 문제 특정노드와 그래프 내 모든 노드 각각의 가장 짧은 경로 찾기 # 전체 쌍 최단 경로 그래프 내 모든 노드 쌍에 대한 최단 경로 찾기 # 다익스트라 알고리즘 - 너비우선 탐색(BFS)과 유사 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리 구하기 (단일 출발 최단 경로 문제) 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를 갱신 # 우선순위 큐를 활용한 다익스트라 알고리즘 초기 첫 정점의 거리는 0, 나머지는 무한대로 저장 우선.. 2021. 4. 9. 이전 1 다음 반응형
